[코테]백준 16236 아기상어 파이썬

https://www.acmicpc.net/problem/16236

이 문제는 기본 BFS에 여러가지 조건이 붙은 문제여서 구현하기가 좀 까다로웠다.

문제의 특징을 몇가지 말해보자면, 

• 아기상어의 위치를 구하고 그 자리를 0으로 초기화 해주기 
• 아기상어의 이동(BFS)와 물고기를 먹으면서 크기를 성장하는 로직을 따로 작성해주기 
• BFS에서 먹은 물고기의 위치, 거리를 리스트로 저장해서 정렬하기 

가 있다. 특히 세번째의 경우 굉장히 중요한 포인트인데, 나는 처음에 BFS로 이동하면 자동으로 제일 위에 있는 물고기, 제일 왼쪽에 있는 물고기부터 먹을줄 알았다. 

"거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다."

이 부분을 어떻게 구현하느냐를 생각하기가 참 애먹었었는데, 간단하게 정렬을 이용하면 되는 것이였다. 

이 복잡한 문제의 전체 코드는 다음과 같다. 

import sys

from collections import deque

read = sys.stdin.readline

N = int(read())

graph = []

for _ in range(N):

    graph.append(list(map(int, read().split())))

for i in range(N):

    for j in range(N):

        if graph[i][j] == 9:

            start_x = i

            start_y = j

            graph[i][j] = 0

dx = [-1,1,0,0]

dy = [0,0,-1,1]

def bfs(x,y,size):

    queue = deque([(x,y,0)])

    visited = [[False for _ in range(N)] for _ in range(N)]

    visited[x][y] = True

    fishes = []

    while queue:

        x,y,dist = queue.popleft()

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:

                if size >= graph[nx][ny]:

                    visited[nx][ny] = True

                    queue.append((nx,ny,dist+1))

                    if 0 <= graph[nx][ny] < size:

                        # 만약 이쪽에서 방문처리를 해주게 되면 먹을 수 있는 물고기만 방문처리하게 되므로, 같은 크기의 물고기나 빈칸은 방문 x

                        fishes.append((dist+1,nx,ny))

    if fishes:

        fishes.sort()

        return fishes[0]

    return None

fish_size = 2

fish_cnt = 0

time = 0

while True:

    result = bfs(start_x,start_y,fish_size)

    if result is None:

        break

    dist, x, y = result

    time += dist

    fish_cnt += 1

    if fish_size == fish_cnt:

        fish_size += 1

    graph[x][y] = 0

    start_x = x

    start_y = y

print(time)