[python] 백준 16236 아기 상어

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

16236번: 아기 상어

 

문제 해결

• 전형적인 이동문제이기 때문에 bfs 또는 dfs를 써야한다는 느낌이 든다.
• 먹이감이 가장 가까이, 왼쪽에 있는 순으로 우선순위가 있으므로 우선순위에 맞게 먹이를 잡으러간다.
• 거리를 기록해야하기 때문에 visited 에 최단 이동 거리를 기록한다.
• 일정 수준 이상 먹으면 크기가 커지는 것을 고려한다.

 

CODE

# 16236 아기상어
from collections import deque

def bfs(i, j):
    dxs = [-1, 0, 0, 1]
    dys = [0, 1, -1, 0]
    visited = [[0] * n for _ in range(n)]
    que = deque()
    que.append((i, j))
    order = []
    visited[i][j] = 1
    while que:
        x, y = que.popleft()
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
                if size[0] > board[nx][ny] and board[nx][ny] != 0:
                    visited[nx][ny] = visited[x][y] + 1
                    order.append((visited[nx][ny] - 1, nx, ny))
                elif size[0] == board[nx][ny]:
                    visited[nx][ny] = visited[x][y] + 1
                    que.append((nx, ny))
                elif board[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    que.append((nx, ny))
    return sorted(order, key=lambda x: (x[0], x[1], x[2]))


if __name__ == "__main__":
    n = int(input())
    board = []
    answer = 0
    for i in range(n):
        x = list(map(int, input().split()))
        for j, num in enumerate(x):
            if num == 9:
                start = (i, j)
        board.append(x)
    size = [2, 0] # 현재 크기, 현재 크기에서 먹은 물고기 개수
    start_x, start_y = start
    while True:
        board[start_x][start_y] = size[0]
        memo = deque(bfs(start_x, start_y))
        if len(memo) == 0:break
        step, nx, ny = memo.popleft()
        answer += step
        size[1] += 1
        if size[0] == size[1]:
            size[0] += 1
            size[1] = 0
        board[start_x][start_y] = 0
        start_x, start_y = nx, ny
    print(answer)