[백준] 16236번: 아기 상어

문제

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

16236번: 아기 상어

 

풀이

BFS(너비 우선 탐색)를 사용해 풀었습니다.

1. 아기 상어의 위치(baby_shark)를 찾아 해당 위치의 값을 0으로 바꾸고 위치를 저장합니다.
2. BFS 함수 내의 fish 리스트에는 같은 거리 상에 있는 먹을 물고기들을 저장합니다.
3. 상하좌우를 확인하며 0 혹은 같은 크기의 물고기는 지나가고, 아기 상어보다 작은 물고기를 fish 리스트에 추가합니다.
4. 만약 먹을 수 있는 물고기가 있다면 물고기를 맨 위쪽, 왼쪽 순으로 정렬해 그 중 첫 번째 물고기를 선택합니다.
5. 총 시간(time)에 걸린 시간(t)을 추가합니다.
6. 그러나, 공간에 더 이상 먹을 수 있는 물고기가 없다면 총 시간(time)을 출력하고 마칩니다.

 

코드

파이썬

import sys
from collections import deque

input = sys.stdin.readline

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

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]


def getStart():
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 9:
                graph[i][j] = 0
                return (i, j)


def BFS(x, y):
    fish = []
    L = 0
    queue = deque()
    visited = [[False] * N for _ in range(N)]
    visited[x][y] = True
    queue.append((x, y))
    while queue:
        for _ in range(len(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 and not visited[nx][ny]:
                    if graph[nx][ny] == 0 or graph[nx][ny] == size:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                    elif graph[nx][ny] < size:
                        visited[nx][ny] = True
                        fish.append((nx, ny))
        L += 1
        if fish:
            fish.sort()
            graph[fish[0][0]][fish[0][1]] = 0
            return [fish[0], L]
    return [[], 0]


time = 0
baby_shark = getStart()
size = 2
eaten = 0

while True:
    baby_shark, t = BFS(baby_shark[0], baby_shark[1])
    if t == 0:
        print(time)
        break
    else:
        time += t
        eaten += 1
        if size == eaten:
            size += 1
            eaten = 0