🥇[백준] 16236 아기 상어 (골드3)

문제요약

나의 코드 및 설명

• bfs() : 아기 상어의 위치로부터 이동할 수 있는 칸의 거리를 v 테이블에 저장
• find() : v 테이블에 저장된 숫자가 가장 작은 칸이 아기 상어로부터 가장 가까운 거리의 칸이므로, 가장 가까운 거리의 물고기를 구하는 함수
• 먹을 수 있는 물고기가 없을 때까지 두 함수를 반복한다.

from collections import deque

#아기 상어의 위치에서부터 이동할 수 있는 칸의 거리를 v 테이블에 저장
def bfs(sx,sy,size):
    queue = deque()
    queue.append((sx,sy))
    v[sy][sx] = 0
    board[sy][sx] = 0

    while 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:
                if v[ny][nx] == -1 and board[ny][nx] <= size:
                    v[ny][nx] = v[y][x] + 1
                    queue.append((nx,ny))

#v 테이블에 저장된 숫자가 가장 작은 칸이 가장 가까운 거리이므로,
#가장 가까운 거리의 물고기 좌표를 구하는 함수
def find(size):
    global distance, feed_x, feed_y
    for i in range(n):
        for j in range(n):
            if v[i][j] != -1 and 0<board[i][j]<size:
                if distance > v[i][j]:
                    distance = v[i][j]
                    feed_x, feed_y = j, i

n = int(input())

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

shark_x, shark_y = 0,0
for y in range(n):
    for x in range(n):
        if board[y][x] == 9:
            shark_x,shark_y = x,y
            break

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

time = 0
size = 2
eat = 0

while True:
    v = [[-1 for _ in range(n)] for _ in range(n)]
    feed_x, feed_y = 0, 0
    distance = 1e9
    bfs(shark_x,shark_y,size)
    find(size)
    if distance == 1e9:
        break
    else:
        time += distance
        shark_x, shark_y = feed_x,feed_y
        board[shark_y][shark_x] = 9
        eat += 1
    
    if eat == size:
        size += 1
        eat = 0

print(time)

피드백

풀 때는 많이 헷갈렸지만, 풀고 나서 보니 풀이 자체가 그렇게 복잡하지는 않았다. 아기 상어의 크기, 크기가 증가하는 조건 등 고려해주는 사항이 많았지만 함수의 파라미터로 주는 등 문제의 조건을 차근차근 구현해서 문제를 해결할 수 있었다.