[시뮬레이션] 백준 16236 Gold3 아기상어

📌 링크 : https://www.acmicpc.net/problem/16236

16236번: 아기 상어

❗️ Issue 

1️⃣ 매번 이동할때마다 상어와 물고기 간 거리를 다시 구해야하는데 어떻게 구하지?

 

💡 Solution 

1️⃣ 한번 먹이를 먹으면 heapq, 방문경로, 거리 초기화, 이후 BFS로 거리 계산

까다로운 문제였다고 생각한다. 

먹이를 먹지 않았을때도 BFS를 돌면서 우선순위큐에 담아야하는데

조건문을 제대로 세우는게 어려웠고 (if 0<data[r][c]<size)

또한 이후에도 BFS에서 d+1을 해주면서 담으면 된다는 걸 생각하지 못했다.

 

그리고 한번 그 자리에서 최소거리의 물고기를 먹으면 초기화한다는 것도 미처 생각지 못했다.

내일 다시 풀어봐야겠다.

import heapq

N = int(input())
data = [list(map(int, input().split())) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
q = []
for i in range(N):
    for j in range(N):
        if data[i][j] == 9:
            data[i][j] = 0
            heapq.heappush(q, (0, i, j))
            break

dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]
size = 2
T = 0
wait = 0
while q:
    d, r, c = heapq.heappop(q)
    # 먹이가 있을떄
    if 0 < data[r][c] < size:  # 0< 주의
        wait += 1
        data[r][c] = 0
        if wait == size:
            size += 1
            wait = 0
        T += d
        # 초기화
        d = 0
        q.clear()
        visited = [[False]*N for _ in range(N)]

    # 먹이가 없을때 혹은 먹이를 먹었을 때
    for i in range(4):
        nr = r+dr[i]
        nc = c+dc[i]
        if not (0 <= nr < N and 0 <= nc < N):
            continue
        if (not visited[nr][nc]) and data[nr][nc] <= size:
            visited[nr][nc] = True
            heapq.heappush(q, (d+1, nr, nc))


print(T)