[백준] 16236 - 아기 상어 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 16236번: 아기 상어

1. 문제

1. N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.
2. 물고기와 아기 상어는 모두 크기를 가지고 있고, 처음 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한칸씩 이동한다.
3. 아기 상어는 자신 보다 큰 물고기 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
4. 아기 상어의 이동 결정 방법은 아래와 같다.
   • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
   • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
   • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
     • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
     • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
5. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
6. 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

2. 풀이

BFS를 이용한 문제 풀이

1. heapq를 통해 물고기의 크기와 위치를 저장한다.
   • heapq의 정렬을 이용해 (물고기의 크기, 물고기의 행, 물고기의 열)을 저장한다.
2. BFS를 통해 상하좌우로 이동 후 거치지 않았던 곳이나 지나갈 수 있는 크기의 칸을 heap에 저장한다.

3. 코드

import heapq
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
di = [[-1,0], [1,0], [0,-1], [0,1]]

def solution():
    heap = []
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 9:
                heapq.heappush(heap, (0, i, j))
                arr[i][j] = 0

    body, eat, ret = 2, 0, 0
    check = [[False] * N for _ in range(N)]
    while heap:
        d, x, y = heapq.heappop(heap)
        if 0 <  arr[x][y] < body:
            eat += 1
            arr[x][y] = 0
            if eat == body:
                body += 1
                eat = 0
            ret += d
            d = 0
            while heap:
                heap.pop()
            check = [[False] * N for _ in range(N)]
        for dx, dy in di:
            nd, nx, ny = d+1, x + dx, y + dy
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if check[nx][ny] or arr[nx][ny] > body:
                continue
            check[nx][ny] = True
            heapq.heappush(heap, (nd, nx, ny))

    return ret

print(solution())

• 결과 : 80 ms

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋