BOJ_16236_아기 상어

너비 우선 탐색(BFS)를 활용하는 구현 문제
while문을 돌면서 물고기를 한 마리씩 잡아먹고, 더 이상 먹을 수 있는 물고기가 없다면 탈출한다

물고기를 잡아먹는 과정에서 BFS를 수행한다. 파이썬에는 우선순위 큐로 활용할 수 있는 heapq가 있는데, 튜플의 왼쪽에 있는 값부터 우선 순위의 대상이 된다

물고기를 잡아먹는 우선 순위는 1. 가까운 순 2. 위에 있는 순 3. 왼쪽에 있는 순이다
그렇기 때문에 (depth, x좌표, y좌표)로 주면 된다

삽질

1. 먹을 수 있는 좌표를 만나자마자 탈출 조건을 줬다. 그렇게 하면 우선순위 큐에 의해 정렬한 후에 가장 순위가 높은 물고기를 먹는 게 아니기 때문에 큐에서 poll 된 후에 탈출 조건을 줘야 한다

2. 방문 처리 좌표를 visited[nx][ny]로 해야 하는데 x, y를 줘서 시간 초과가 되고 있었다

3. 물고기의 현재 위치를 배제하고 먹을 수 있는 지를 봐야 하는데 예외처리를 안 했다

잘 하자~~

import heapq  
  
# 아기상어 좌표에서 상하좌우로만 이동할 수 있음  
# 상 - 좌 - 우 - 하 로 탐색하면 가장 왼쪽 위에 있는 거부터 먹을 수 있음  
  
N = int(input())  
weight = 2  
eaten_fish = 0  
timer = 0  
dx = [-1, 0, 0, 1]  
dy = [0, -1, 1, 0]  
space = []  
  
  
# 입력  
def input_space():  
    x = -1  
    y = -1  
    for i in range(N):  
        space.append(list(map(int, input().split())))  
  
        if 9 in space[i]:  
            x = i  
            y = space[i].index(9)  
  
    return [x, y]  
  
  
def find_fish(sx, sy):  
    visited = [[False] * N for _ in range(N)]  
    hq = []  
    heapq.heappush(hq, (0, sx, sy))  
    visited[sx][sy] = True  
  
    while hq:  
        depth, x, y = heapq.heappop(hq)  
  
        if not (sx == x and sy == y) and 0 < space[x][y] < weight:  
            return [x, y, depth]  
  
        for i in range(4):  
            nx = x + dx[i]  
            ny = y + dy[i]  
  
            if nx < 0 or ny < 0 or nx >= N or ny >= N or visited[nx][ny] or space[nx][ny] > weight:  
                continue  
  
            visited[nx][ny] = True  
            heapq.heappush(hq, (depth + 1, nx, ny))  
  
    return None  
  
  
x, y = input_space()  
  
while True:  
    target_idx = find_fish(x, y)  
  
    if target_idx is None:  
        break  
  
    space[x][y] = 0  
    x = target_idx[0]  
    y = target_idx[1]  
    timer += target_idx[2]  
    eaten_fish += 1  
    space[x][y] = 9  
  
    if eaten_fish == weight:  
        weight += 1  
        eaten_fish = 0  
  
print(timer)