1 minute read

문제

접근 방법

BFS를 통해서 제일 가까운 물고기를 먹으면서 진행하면 된다고 생각했다. N<=20이라 BFS를 20번 한다고 해도 $\ 20^3 $이라 조건을 만족시키게 BFS를 편하게 반복해도 된다고 생각했다.

우선 상어의 좌표 (시작점)과 총 물고기의 개수를 받아야 한다고 생각했다. 문제 조건에서 물고기의 개수가 0일 때 상황을 종료해도 된다고 해서 이 값을 갖고 있어야 한다고 생각했다.

bfs를 통해서 현재 좌표에서 먹을 수 있는 물고기들을 구해서 list로 반환하였다. 동일한 크기를 가진 물고기가 존재할 경우에 문제에서 제시한 기준대로 정렬하여 조건을 제일 만족하는 물고기만 먹게 했다.

정답 코드


import sys
from collections import deque
input = sys.stdin.readline

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

shark_h, shark_w = 0,0
fishes = 0
for i in range(n):
    for j in range(n):
        if maps[i][j] == 9:
            shark_h, shark_w = i,j
        elif 0<maps[i][j] < 9:
            fishes += 1

"""
bfs를 통해 현재 먹을 수 있는 물고기들을 다 구함
물고기들 중에서 조건에 적합한 물고기를 먹고 그 좌표로 이동
이를 fishes 수가 0이거나 크기가 모두 자기보다 크거나 같을 경우일때 멈춤
"""

moves = ([-1,0], [1,0], [0,1], [0,-1])
def bfs(start_h, start_w, size):
    avails = []
    q = deque()
    q.append((start_h, start_w,0))
    visited = set()
    visited.add((start_h, start_w))
    while q:
        h,w,d = q.popleft()
        for dh, dw in moves:
            new_h, new_w, new_d = h+dh, w+dw, d+1
            if 0<=new_h<n and 0<=new_w<n and (new_h, new_w) not in visited and maps[new_h][new_w] <= size:
                q.append((new_h, new_w, new_d))
                visited.add((new_h, new_w))
                #먹을 수 있는 물고기 배열에 추가
                if 0 < maps[new_h][new_w] < size:
                    avails.append((new_h, new_w, new_d))
    avails.sort(key = lambda x: (x[2], x[0], x[1]))
    return deque(avails)

size = 2
cnt = 0 #크기가 변할 때마다 초기화되는 물고기 수
total_time = 0
while True:
    fish = bfs(shark_h, shark_w, size)
    #먹을 수 있는 물고기가 없거나 물고기 수가 0일때
    if not fish or fishes == 0:
        break

    #물고기 먹기
    f = fish.popleft()
    fishes -= 1
    cnt+=1
    total_time += f[2]
    #시작점도 0으로 
    maps[shark_h][shark_w] = 0
    shark_h, shark_w = f[0], f[1]
    #먹은 물고기는 이제 0으로 바꿔야함
    maps[shark_h][shark_w] = 0

    #먹은 물고기 수가 크기와 같다면 size 키움
    if cnt == size:
        size+=1
        cnt = 0
    #시작점 초기화


print(total_time)

느낀 점

다른 문제들은 BFS를 통해 최단경로 길이를 사용해서 문제를 진행하는데 이 문제는 BFS응 통해서 갈 수 있는 후보들을 구하여 문제를 진행해야 됐다. 이 문제를 통해서 BFS를 활용해야 하는 새로운 유형을 경험했다.

You May Also Enjoy