[BAEKJOON] 16236번. 아기 상어

 

---

 

## DFS로 풀었을 때 ##

'''
조건
1. 아기상어의 크기: 2, 크기랑 똑같은 수의 물고기 먹으면 크기 +1
2. 구하고자 하는 것: 몇초동안 SOS 안치고 먹을 수 있는지
3. 가까운 물고기 먹으러 간다. > 가장 위에 있는 물고기 먹으러 간다. > 가장 왼쪽 먹으러 간다.
4. 자기 크기보다 작은 물고기만 먹을 수 있음 (같으면 먹지는 못하고 움직일 순 있음)
'''

def dfs(sx, sy, d):     # dfs: 먹을 물고기 정하기, d: 물고기와의 거리
    global target, min_d

    # d > min_d라면 걍 return
    if d >= min_d:
        return
    # 먹을 수 있는 물고기 크기 생각해보기
    if 0 <= space[sx][sy] < shark_size:     # 공간 내 물고기 크기가 상어보다 작으면
        if d < min_d:       # 훨씬 가까운 물고기
            min_d = d
            target = (sx, sy)

        elif d == min_d:     # 거리가 같은 물고기
            if (sx < target[0]) or (sx == target[0] and sy < target[1]):
                target = (sx, sy)       # 거리가 같은 물고기는 우선순위에 따라 처리
        return
    # 이동하기
    for i in range(4):
        nx, ny = sx+dx[i], sy+dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            # 방문한 적 없고 + 상어 크기보다 크면 안됨
            if not visited[nx][ny] and space[nx][ny] <= shark_size:
                visited[nx][ny] = True
                dfs(nx, ny, d+1)
                visited[nx][ny] = False


N = int(input())
space = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# 상어 좌표 구하기
for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            x, y = i, j
            space[i][j] = 0

shark_size = 2      # 상어 크기
eat = 0             # 상어가 먹은 물고기 수
answer = 0          # 총 걸린 시간 (1초에 1칸 움직임)

while True:
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    
    min_d = float('inf')
    target = None  # 상어가 먹을 물고기(타겟)

    dfs(x, y, 0)    # 먹을 물고기 구햇음

    if not target:
        break

    tx, ty = target
    eat += 1
    answer += min_d

    if shark_size == eat:       # 크기만큼 먹으면 크기 +1
        shark_size += 1
        eat = 0

    space[tx][ty] = 0           # 먹은 물고기 위치로 이동 (1)
    x, y = tx, ty               # 먹은 물고기 위치로 이동 (2)

print(answer)

솔직히 DFS로 풀었을 때 왜 이렇게 되는지 제대로 이해도 못했는데 시간 초과까지 일어남. 이렇게 된 거 그냥 BFS로 푸는 법을 알아야 할 듯.

## BFS 코드 ##

'''
조건
1. 아기상어의 크기: 2, 크기랑 똑같은 수의 물고기 먹으면 크기 +1
2. 구하고자 하는 것: 몇초동안 SOS 안치고 먹을 수 있는지
3. 가까운 물고기 먹으러 간다. > 가장 위에 있는 물고기 먹으러 간다. > 가장 왼쪽 먹으러 간다.
4. 자기 크기보다 작은 물고기만 먹을 수 있음 (같으면 먹지는 못하고 움직일 순 있음)
'''
from collections import deque

def bfs(shark_size, x, y):
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    q = deque()
    q.append((x, y, 0))     # 좌표 및 거리

    min_x = float('inf')
    min_y = float('inf')
    min_time = float('inf')

    while q:        # 큐에 뭔가가 있을 때까지
        cx, cy, time = q.popleft()
        
        # 먹을 수 있는 물고기 발견: 상어 크기보다 작고 + 제일 가까운 위치 (= 짧은 시간)
        if (0 < space[cx][cy] < shark_size) and (time <= min_time):
            if time < min_time:
                min_time = time
                min_x, min_y = cx, cy
            elif time == min_time:
                # 가장 위에 있는 물고기 -> 가장 왼쪽에 있는 물고기
                if (cx < min_x) or (cx == min_x and cy < min_y):
                    min_time = time
                    min_x, min_y = cx, cy
        
        for i in range(4):      # 4방향 탐색 시작 => 이동 가능한지
            nx, ny = cx+dx[i], cy+dy[i]
            # 물고기가 있는 공간의 범위를 벗어나지 않아야 함
            if 0 <= nx < N and 0 <= ny < N:
                # 방문한 적 없고 + 상어 크기보다 같거나 작아야 함
                if not visited[nx][ny] and space[nx][ny] <= shark_size:
                    visited[nx][ny] = True
                    q.append((nx, ny, time+1))
    
    return (min_x, min_y, min_time)


N = int(input())        # space의 크기: N * N
space = [list(map(int, input().split())) for _ in range(N)]     # 물고기가 있는 공간
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            x, y = i, j
            space[i][j] = 0
            break

shark_size = 2
eat_count = 0
total_time = 0

while True:     # 시뮬레이션 시작
    nx, ny, time = bfs(shark_size, x, y)    # 먹을 물고기 찾아서 이동
    if time == float('inf'):
        break

    space[nx][ny] = 0   # 물고기 먹음
    x, y = nx, ny       # 물고기 자리 차지

    eat_count += 1
    total_time += time

    if eat_count == shark_size:
        shark_size += 1
        eat_count = 0
    
print(total_time)

DFS, BFS의 차이일 뿐인데 결과의 차이가 명백하구나.. 쩝...

조만간 지금까지 본 백준 문제 다시 백지상태에서 코드 짜는 연습해야 할 듯.