[백준 16236] 아기 상어

문제 보기

이 문제는 백준에 알고리즘 분류가 따로 되어있지 않지만 나는 BFS로 푼 문제이다.

상어가 먹을 물고기를 찾기 위해서 BFS를 사용하였고, 상어가 어디로 이동할 지 결정하는 방법은 다음과 같다.

먹을 물고기를 정하기 위해서 나는 우선순위 큐(Priority Queue)를 사용했다.

문제를 풀기 위한 로직은 다음과 같다.

1. 현재의 상어위치로부터 BFS를 시작한다. (17~20번째 줄)

2. BFS를 진행하면서, 상어가 지나갈 수 있으면 현재까지의 거리, 행과 열을 큐에 넣고, 먹을 수 있는 물고기가 있으면 우선순위 큐에 우선순위를 현재까지의 거리, 행, 열 순으로 삽입한다. (30~36번째 줄)

3-1. 우선순위 큐가 비어있으면(=먹을 수 없는 물고기가 없으면) 종료한다. (38~40번째 줄)

3-2. 우선순위 큐가 비어있지 않으면, 물고기의 위치로 상어를 이동시키고, 물고기를 잡아먹는다. 이 때, 잡아먹은 물고기의 갯수가 상어의 크기와 똑같다면 상어의 크기를 1 증가시킨다.

위 과정을 반복하면 된다.

BFS와 우선순위 큐를 사용했지만 3788ms가 걸렸다.. 원인이 무엇인지 잘 모르겠다..

import sys
from collections import deque
from queue import PriorityQueue
 
n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for c in range(n)]
 
shark_r, shark_c, shark_size, eat_count = 0, 0, 2, 0
for r in range(n):
    for c in range(n):
        if board[r][c] == 9:
            shark_r, shark_c = r, c
 
answer = 0
directions = ((-1, 0), (0, 1), (1, 0), (0, -1))
while True:
    q = deque()
    q.appendleft([0, shark_r, shark_c])
    pq = PriorityQueue()
    visited = set([(shark_r, shark_c)])
    while q:
        dist, cur_r, cur_c = q.pop()
        
        for dr, dc in directions:
            next_r = cur_r + dr
            next_c = cur_c + dc
            
            if 0 <= next_r < n and 0 <= next_c < n:
                if (next_r, next_c) not in visited:
                    # if a shark can pass
                    if board[next_r][next_c] <= shark_size:
                        # if the fish is eatable
                        if 0 < board[next_r][next_c] < shark_size:
                            pq.put((dist + 1, next_r, next_c))
                        q.appendleft([dist + 1, next_r, next_c])
                        visited.add((next_r, next_c))
    
    qsize = pq.qsize()
    if qsize == 0:
        break
    elif qsize > 0:
        dist, fish_r, fish_c = pq.get()
        # move shark
        board[shark_r][shark_c] = 0
        shark_r, shark_c = fish_r, fish_c
        board[shark_r][shark_c] = 9
        # eat fish
        eat_count += 1
        if eat_count == shark_size:
            shark_size += 1
            eat_count = 0
        answer += dist
print(answer)