아기 상어 [백준 16236번]

문제

 

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

16236번: 아기 상어

 

내 풀이

 

bfs를 사용하여 아기 상어와 모든 물고기 간의 거리를 구하였다.

이동할 때 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다는 조건을 고려하였다.

그러나 아기 상어가 먹을 수 있는 물고기 리스트인 fishes에 넣을 때에는 물고기의 크기가 아기 사어의 크기보다 작은지 확인하였다. 같으면 fishes에 들어갈 수 없기 때문이다.

 

fishes를 조건에 따라 정렬하였다.

거리가 가까운 물고기부터 -> 가장 위에 있는 물고기부터 -> 가장 왼쪽에 있는 물고기부터

 

그리고 fishes에서 물고기를 한 마리 꺼낸 후 아기 상어의 크기를 조정할 수 있으면 조정해주었다.

 

마지막으로 시간을 구해야 하는데, 여기서 정신을 똑바로 차려야 한다.

time에는 1초가 아닌, 아기 상어와 물고기 사이의 거리(=초)를 더해주어야 한다.

 

from collections import  deque
N = int(input())
bowl = []
sx, sy = 0, 0
for i in range(N):
    arr = list(map(int, input().strip().split()))
    bowl.append(arr)
    for j in range(N):
        if arr[j] == 9:
            sx, sy = i, j
bowl[sx][sy] = 0
shark_size = 2
cnt = 0
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
def bfs(x, y):
    global sx, sy, cnt, shark_size
    dist = [[-1] * N for _ in range(N)]
    fishes = []
    q = deque()
    q.append((x, y))
    dist[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if dist[nx][ny] == -1 and bowl[nx][ny] <= shark_size:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
                    if 0 < bowl[nx][ny] < shark_size:
                        fishes.append(((nx, ny), dist[nx][ny]))
    fishes.sort(key=lambda x:(x[1], x[0][0], x[0][1]))
    if fishes:
        pos, d = fishes.pop(0)
        fx, fy = pos
        sx, sy = fx, fy
        bowl[fx][fy] = 0
        cnt += 1
        if cnt == shark_size:
            shark_size += 1
            cnt = 0
        return d
    else:
        return -1
time = 0
while True:
    d_time = bfs(sx, sy)
    if d_time == -1:
        break
    else:
        time += d_time
print(time)

 

총평

삼며든다...