문제 링크

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

문제 설명

• 자신보다 작은 물고기를 한 마리씩 잡아먹음
• 우선순위
  • 가장 가까운 물고기 우선
  • 가장 위에 있는 물고기 우선
  • 가장 왼쪽에 있는 물고기 우선
• 자신의 크기의 수 만큼 잡아먹으면 크기 1 커짐
• 가능한 물고기를 모두 잡아먹는 시간 출력

풀이

• BFS로 이동하면서 거리별로 잡아먹을 수 있는 물고기 위치를 따로 저장해줬다
• 가장 가까운 물고기들을 y, x로 정렬 후 리턴

코드

import sys
from collections import deque

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

def solution():
    global n, board
    read = sys.stdin.readline
    n = int(read())
    board = [list(map(int, read().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if board[i][j] == 9:
                cy, cx = i, j
                board[cy][cx] = 2
    t, count= 0, 0
    while True:
        # 다음 위치 찾기
        ny, nx, dist = bfs(cy, cx)
        if not dist:
            break
        count += 1
        # 크기 증가
        if count == board[cy][cx]:
            board[cy][cx] += 1
            count = 0
        # 이동
        board[ny][nx] = board[cy][cx]
        board[cy][cx] = 0
        cy, cx = ny, nx
        t += dist
    print(t)

def bfs(sy, sx):
    dist = [[] for _ in range(n**2)]
    visited = [[0] * n for _ in range(n)]
    visited[sy][sx] = 1
    q = deque([[sy, sx, 0]])
    while q:
        cy, cx, cd = q.popleft()
        for d in range(4):
            ny, nx = cy + dy[d], cx + dx[d]
            if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx]:
                if 0 <= board[ny][nx] <= board[sy][sx]:
                    q.append([ny, nx, cd+1])
                    visited[ny][nx] = 1
                    # 크기별 위치 저장
                    if 0 < board[ny][nx] < board[sy][sx]:
                        dist[cd+1].append([ny, nx, cd+1])
    # 가장 가까운 위치 리턴
    for d in range(n**2):
        if dist[d]:
            dist[d].sort()
            return dist[d][0]
    return 0,0,0

solution()