[백준] 16236번, 아기상어 (Python)

문제

 

코드

import collections

n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
dx,dy = [-1,1,0,0], [0,0,-1,1]
answer = 0
size = 2
exp = 0

def bfs(a,b,size):
    queue = collections.deque()
    queue.append((a,b))
    visited[a][b] = True
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if (graph[nx][ny] == size or graph[nx][ny] == 0) and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx,ny))
                elif graph[nx][ny] < size and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx,ny))
                    result.append([distance[nx][ny], nx, ny])
while True:
    result = []
    visited = [[False]*n for _ in range(n)]
    distance = [[0]*n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            if graph[x][y] == 9:
                bfs(x,y,size)
                graph[x][y] = 0
    if result:
        result.sort()
        dis,r_x,r_y = result.pop(0)
        exp += 1
        answer += dis
        graph[r_x][r_y] = 9
    else:
        break
    if exp == size:
        size += 1
        exp = 0
print(answer)

 

아기상어는 자기보다 크기가 작은 물고기를 먹을 수 있고 크기가 같다면 지나갈 수만 있고 크기가 자신보다 크다면 지나갈 수 없다.

 

bfs를 돌면서 자신보다 크기가 작은 물고기(먹을수 있는 물고기)를 만나면 result 리스트에 거리, x좌표, y좌표 순으로 넣어준다.

 

result 리스트를 sort 정렬 시켜서 가장 거리가 짧은 물고기를 먹고 (거리가 같다면 x좌표, y좌표 순으로 오름차순 정렬된다.) exp를 +1 해주고 만약 exp와 size가 같다면 size를 1 증가시켜 준다.

 

아기상어가 먹을수 있는 물고기가 없을때 까지 계속 돌아주고 아기상어가 물고기를 잡아먹은 시간은 이동거리와 똑같으므로 distance배열로 구해줬다.