[파이썬 PYTHON] 백준 16236번 【아기 상어】

---

import sys
import copy
from collections import deque

# 예제 입력
N = int(input())
_map = [[0]*N for _ in range(N)]
checked = [[False]*N for _ in range(N)]
queue = deque([])


for i in range(N):
    info = list(map(int,sys.stdin.readline().split()))
    for j in range(N):
        _map[i][j]=info[j]
        if info[j] == 9:
            _map[i][j] = 0
            shark = [i,j,0]
            queue.append(shark)


# bfs()로 먹을 수 있는 먹이 탐색하기

dr = [1,-1,0,0]
dc = [0,0,1,-1]

fish = []
def bfs(sharkSize):
    copiedMap = copy.deepcopy(_map)
    copiedCheck = copy.deepcopy(checked)
    while len(queue) !=0:
        r,c,t = map(int,queue.popleft())
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            nt = t + 1
            if 0<=nr<N and 0<=nc<N and copiedMap[nr][nc]<=sharkSize and not copiedCheck[nr][nc]:

                queue.append([nr,nc,nt])
                copiedCheck[nr][nc]=True

                if 0< copiedMap[nr][nc] <sharkSize:
                    fish.append([nr,nc,nt])
    if fish:
        fish.sort(key = lambda x : (x[2],x[0],x[1]))
        return fish[0]
    else:
        return None

sharkSize = 2
food = 0
ans = 0
while True:
    fish.clear()
    result = bfs(sharkSize)
    if result:
        r,c,t = map(int,result)
        food +=1
        if sharkSize == food:
            sharkSize+=1
            food = 0
        _map[r][c]=0
        queue.append([r,c,0])
        ans+=t
    else:
        break
print(ans)

약 2시간에 걸쳐서 혼자 해결한 문제!

 

문제 접근 방법

1. bfs()로 상어가 먹을 수 있는 먹이의 위치와 그 위치에 도달한 시간을 모두 기록 (fish stack에 입력)

2. 먹이 우선순위에 따라, 입력된 먹이(fish)를 시간순으로(=거리) 오름차순 정렬, 행을 기준으로 오름차순 정렬, 열을 기준으로 오름차순 정렬 후 첫번째에 위치한 먹이를 return 한다.

 

만약, 먹이가 존재하지 않는다면 None 을 return 한다.

 

3. bfs() 이후 정상적으로 반환이 되었다면, 먹은 물고기 양을 기록하고 물고기 양에 따라 상어 크기도 변경한다.

먹이를 먹은 위치가 상어 위치가 되므로 queue 에 추가하고 bfs()를 다시 실행한다.

 

💡 주의점. bfs()를 하기 전에 fish 스택을 비워준다.