[BOJ16236 - Python] 아기 상어

문제

---

16236번: 아기 상어

 

N×N 공간에 물고기 M마리와 아기 상어 1마리가 있다.

처음에 아기 상어의 크기는 2, 1초에 상하좌우로 인접한 한 칸씩 이동한다.

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.

자신의 크기보다 작은 물고기만 먹을 수 있기에, 크기가 같은 물고기는 먹을 수 없고 지나갈 수는 있다.

 

아기 상어는 자신의 크기와 같은 수의 물고리를 먹을 때마다 크기가 1 증가한다.

 

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

 

1. 더 이상 먹을 수 있는 물고기가 공간에 없다면 엄마 상어에게 도움을 요청한다.

2. 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 간다.

3. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

     * 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때 거리는 지나야 하는 칸의 개수의 최솟값

     * 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기 / 그러한 물고기가 여러 마리라면 가장 왼쪽에 있는 물고기를 먹는다.

 

물고기를 먹는 시간은 없다고 가정했을 때

아기 상어가 몇 초동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지를 구하는 것이 문제이다.

 

 

풀이

---

먼저 아기 상어의 위치를 알아야 한다. 공간에 대한 입력에서 아기 상어의 위치는 9로 주어진다.

 

fish라는 이차원 배열에 입력값들(칸에 있는 물고기의 크기)을 바로 저장하면서 아기 상어의 위치 좌표를 변수 y, x에 저장해주었고,

fish 배열 상에서 아기 상어가 있는 부분은 0으로 저장해주었다.

# 아기 상어 위치
y, x = 0, 0

fish = []
for i in range(N):
    fish.append(list(map(int, sys.stdin.readline().split())))
    if 9 in fish[i]:
        y = i
        x = fish[i].index(9)

fish[y][x] = 0

 

해당 문제를 해결하기 위해 BFS를 이용하였는데,

아기 상어의 현재 위치에서 거리가 가까운 물고기를 먼저 탐색해야 하기 때문에 우선순위 큐를 사용하였다.

 

우선순위 큐에는 (아기 상어가 지금까지 이동한 거리, 아기 상어의 y좌표, 아기 상어의 x좌표) 순서로 튜플이 저장된다.

(우선순위 큐에서 하나의 원소에 여러 자료가 들어가있는 경우, 디폴트로 첫 번째 자료를 기준으로 정렬된다.)

 

거리가 가까운 물고기가 많다면 가장 위에 있는 물고기 / 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹는다는 조건이 있었다.

이에 아기 상어가 주변을 탐색하는 순서는 상, 좌, 하, 우로 설정하였다.

dy = (-1, 0, 1, 0)
dx = (0, -1, 0, 1)

 

BFS의 큰 틀은 다음과 같다.

 

1. 아기 상어의 현재 위치에서 주변을 탐색한다.

아기 상어가 이동했을 때 물고기가 아기 상어의 크기보다 작거나 같아 그 위치로 이동할 수 있다면

visited 배열에 해당 위치를 방문했음을 기록, 우선순위 큐에 push 한다.

d, y, x = heapq.heappop(q)

...

for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and fish[ny][nx] <= size:
        visited[ny][nx] = True
        heapq.heappush(q, (d + 1, ny, nx))  # 이동 거리 + 1

 

2. 우선순위 큐를 pop했을 때 push 된 것들 중 가장 짧은 이동 거리를 가지는 요소가 pop 된다.

해당 위치에 있는 물고기가 먹을 수 있는 물고기라면 바로 잡아먹는다.

(아기 상어는 자신의 크기와 같은 수의 물고리를 먹을 때마다 크기가 1 증가한다는 조건 주의)

if 0 < fish[y][x] < size:  # 먹을 수 있는 물고기인 경우
    eat += 1  # 먹은 횟수 + 1
    fish[y][x] = 0
    if size == eat:  # 자신의 크기와 같은 수의 물고기를 먹었을 경우
        size += 1
        eat = 0
    ans += d  # 총 이동 거리를 저장하는 변수에 해당 이동 거리를 저장

 

그 후

(1) 현재까지 이동한 거리 d를 0으로 초기화

(2) visited 배열을 전부 초기화 (이동했던 위치로 다시 이동할 수 있기 때문)

(3) 우선순위 큐도 초기화

# 초기화
d = 0
while q:
    heapq.heappop(q)
visited = [[False for _ in range(N)] for _ in range(N)]

그러고 나서 현재의 위치부터 다시 주변을 탐색한다.

 

코드

---

import sys
import heapq

N = int(sys.stdin.readline().strip())

# 아기 상어 위치
y, x = 0, 0

fish = []
for i in range(N):
    fish.append(list(map(int, sys.stdin.readline().split())))
    if 9 in fish[i]:
        y = i
        x = fish[i].index(9)

fish[y][x] = 0

dy = (-1, 0, 1, 0)
dx = (0, -1, 0, 1)


def BFS(r, c):
    ans = 0
    size = 2  # 아기 상어의 크기
    eat = 0  # 먹은 횟수

    q = []
    heapq.heappush(q, (0, r, c))  # 거리, y좌표, x좌표
    visited = [[False for _ in range(N)] for _ in range(N)]

    while q:
        d, y, x = heapq.heappop(q)

        if 0 < fish[y][x] < size:  # 먹을 수 있는 물고기인 경우
            eat += 1
            fish[y][x] = 0
            if size == eat:  # 자신의 크기와 같은 수의 물고기를 먹었을 경우
                size += 1
                eat = 0
            ans += d

            # 초기화
            d = 0
            while q:
                heapq.heappop(q)
            visited = [[False for _ in range(N)] for _ in range(N)]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and fish[ny][nx] <= size:
                visited[ny][nx] = True
                heapq.heappush(q, (d + 1, ny, nx))
    return ans


print(BFS(y, x))