16236 아기상어 파이썬

백준 아기상어 : https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

작성한 코드

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
mapp = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(i, j, size):
    dist = [[-1] * N for _ in range(N)]
    q = deque()
    q.append((i, j))
    dist[i][j] = 0
    ans = []

    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if 0 <= nx < N and 0<= ny < N and dist[nx][ny] == -1:
                move_ok = False
                eat = False
                if mapp[nx][ny] == 0:
                    move_ok = True
                elif size == mapp[nx][ny]:
                    move_ok = True
                elif size > mapp[nx][ny]:
                    move_ok = True
                    eat = True
                if move_ok:
                    q.append((nx, ny))
                    dist[nx][ny] = dist[x][y] +1
                    if eat:
                        ans.append((dist[nx][ny], nx, ny))
    if not ans:
        return None
    ans.sort()
    return ans[0]


shark_exp = 0
shark_size = 2
for i in range(N):
    for j in range(N):
        if mapp[i][j] == 9:
            x, y = i, j
            mapp[i][j] = 0

answer = 0
while True:
    fish = bfs(x, y, shark_size)
    if fish is None:
        break
    temp_dist, temp_x, temp_y = fish
    answer += temp_dist
    mapp[temp_x][temp_y] = 0
    shark_exp += 1
    if shark_size == shark_exp:
        shark_size += 1
        shark_exp = 0
    x, y = temp_x, temp_y
print(answer)

 

문제에 상어가 물고기를 먹으러 이동할 때 지나야하는 칸의 개수가 최소여야 한다고도 하고 상하좌우로 인접한

한 칸씩 이동한다고 하는걸 보니 BFS문제라고 생각이 들었다.

 

bfs로 가장 가까운 물고기를 먹고 그 물고기의 거리가 같으면 가장 위에 있는 물고기, 여러마리라면 왼쪽에 있는

물고기를 먹어야한다고해서 bfs에서 상어의 시작지점에서 bfs를 다 해주고 구한 ans값에 정렬을 한다

나중에 알고보니 가장 위에 있는 물고기, 그다음으로 왼쪽 물고기 이게 index로 정렬이 되면 딱 구현이 된다

상어가 물고기를 먹고 새롭게 먹은 자리에서 다시 bfs를 돌려주면서 거리를 계속 더해나가는 구조이다.