16236번. 아기 상어

http://boj.kr/16236 

 

 

 

가장 가까운 물고기는 BFS로 찾는다. 코드 내에서 fishes 리스트가 그것이다.

새로운 물고기를 먹을 때마다 상어의 위치가 변경되므로 fishes 리스트를 매번 갱신한다.

itemgetter를 이용해 물고기를 거리, row, col 순으로 손쉽게 정렬해줄 수 있다.

상어의 크기가 증가하는 규칙이 상어의 크기 += 물고기의 크기가 아니라,

상어 크기=지금까지 먹은 누적 물고기 갯수(in_belly) 일때마다 상어의 크기가 1씩 늘어난다는 점에 유의하자. 당연히 상어 크기가 늘어났으면 in_belly를 0으로 초기화해야 답이 나온다.

import sys
from collections import deque
from operator import itemgetter


def get_distance(shark):
    fishes = []
    visited = [[0] * N for _ in range(N)]
    visited[shark[ROW]][shark[COL]] = 1
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    queue = deque([[shark[ROW], shark[COL], 0]])
    while queue:
        r, c, dist = queue.popleft()
        for i in range(4):
            next_r = r + dx[i]
            next_c = c + dy[i]
            if 0 <= next_r < N and 0 <= next_c < N:
                if not visited[next_r][next_c]:
                    if board[next_r][next_c] <= shark[SIZE]:  # 지나갈 수 있는 물고기
                        if 0 < board[next_r][next_c] < shark[SIZE]:  # 먹을 수 있는 물고기
                            fishes.append([next_r, next_c, board[next_r][next_c], dist+1])
                        visited[next_r][next_c] = 1
                        queue.append([next_r, next_c, dist+1])

    fishes.sort(key=itemgetter(DIST, 0, 1))  # 거리, row, column 순으로 정렬
    return fishes


def start(shark):
    global in_belly
    
    sec = 0
    while True:
        fishes = get_distance(shark)
        if not fishes:  # 물고기가 없으면 종료
            print(sec)
            break
        prey = fishes[0]  # 희생양 물고기

        in_belly += 1
        if shark[SIZE] == in_belly:
            shark[SIZE] += 1
            in_belly = 0

        shark = [prey[ROW], prey[COL], shark[SIZE]]  # 상어 정보 업뎃
        board[prey[ROW]][prey[COL]] = 0
        sec += prey[DIST]
        del fishes[0]
    return


if __name__ == '__main__':
    ROW, COL, SIZE, DIST = 0, 1, 2, 3
    input = sys.stdin.readline
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    shark_sz = 2  # 상어의 기본 크기는 2
    in_belly = 0  # 누적된 먹은 물고기 갯수
    
    for i in range(N):
        for j in range(N):
            if board[i][j] == 0:
                continue
            elif board[i][j] == 9:  # 상어
                shark_init = [i, j, shark_sz]
                board[i][j] = 0  # 나중에 물고기로 착각하지 않도록 0으로 변경

    start(shark_init)