Baekjoon 16236번 아기 상어

문제

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

걸린 시간

01 : 24 : 23

풀이

Python3

from collections import deque

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

def bfs(shark, size):
    q = deque()
    r, c = shark
    q.append([r, c])
    visited[r][c] = True
    move = 0
    can_eat = []

    while q:
        if len(can_eat) > 0:
            break

        move += 1

        for _ in range(0, len(q)):
            x, y = q.popleft()
            # 잡아먹을 수 있다면
            if 0 < space[x][y] < size:
                can_eat.append([x, y])
            else:
                for i in range(0, 4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < N and 0 <= ny < N:
                        if not visited[nx][ny] and space[nx][ny] <= size:
                            visited[nx][ny] = True
                            q.append([nx, ny])

    # 반환할 값 : 상어의 이동횟수, 좌표
    if len(can_eat) == 0:
        return 0, shark
    elif len(can_eat) == 1:    
        return move-1, can_eat[0]
    else:
        can_eat = sorted(can_eat)    
        return move-1, can_eat[0]

if __name__ == "__main__":
    N = int(input())

    space = []

    for i in range(0, N):
        row = list(map(int, input().split()))
        space.append(row)
        for j in range(0, N):
            if row[j] == 9:
                shark = [i, j]
                row[j] = 0

    size = 2
    result = 0
    count = 0
    while True:
        visited = [[False for _ in range(0, N)] for _ in range(0, N)]
        move, shark = bfs(shark, size)
        x, y = shark
        space[x][y] = 0
        if move == 0:
            break
        else:
            result += move
            count += 1

        if count == size:
            count = 0
            size += 1

    print(result)

BFS 로 간단하게 풀이했다. 문제 해석에 걸리는 시간만 줄이면 될 것 같다.