[solved.ac 골드3] 16236_아기 상어 (파이썬, 구현, BFS)

제한 사항

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

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

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

예제

---

나의 풀이

문제가 길고 주어진 조건이 많아서 다음과 같이 정리해보았다.

[주어진 것]

• 바다: N x N 크기 (2 <= N <= 20) (문제에서 정사각형 공간이라고 했지만 바다라고 부르겠다)
  • 0 : 빈 칸
  • 1, 2, 3, 4, 5, 6 : 물고기 크기
  • 9 : 아기 상어의 위치
• 아기 상어 1마리, 물고기 여러 마리

[초기값 & 정해진 값]

• 아기 상어 크기 : 2
• 이동 속도 : 1 
• 이동 범위 : 상 하 좌 우

[이동 방법]

• 더 이상 먹을 수 있는 물고기가 없다면 종료
• 먹을 수 있는 물고기가 있다면 가까운 물고기 먹음 (한 마리 남았을 때 먹는다는 조건도 이 조건에 포함됨)

[물고기까지의 거리]

• 물고기까지의 거리 : 상 하 좌 우로 움직이면서 거쳐가는 칸의 수
• 우선 순위 
  1. 가장 위
  2. 가장 왼쪽

[아기 상어의 이동]

• 자신보다 큰 물고기는 지나갈 수 없다. (크기가 같으면 지나갈 수 있음)
• 자신보다 작은 물고기만 먹을 수 있다. (크기가 같으면 못 먹음)

[추가 사항]

• 자신(아기 상어)의 크기와 같은 수의 물고기를 먹을 때마다 자신의 크기 1 증가
• ex) 현재 상어 크기가 4라면 4마리의 물고기를 먹으면 크기가 5가 됨

[출력]

• 잡아먹을 물고기가 없을 때까지 돌아다닌 거리 (=시간)

---

우선 상어가 먹을 수 있는 물고기를 찾는 과정이 필요하다. 이때 자신보다 작으면서 가장 가까운 물고기를 먹을 수 있고 거리가 같은 물고기가 많다면 가장 위, 가장 왼쪽의 물고기의 우선순위가 더 높다는 조건이 있기 때문에 먹을 수 있는 가장 가까운 물고기들을 구하는 풀이이 필요하다.

가장 적합하다고 생각된 것이 BFS이다. 너비 우선 탐색을 하며 먹을 수 있는 물고기들의 리스트를 구한 후 그 중 가장 우선 순위가 높은 물고기 위치로 이동해 물고기를 먹는다.

만약 현재 아기 상어 위치에서 BFS 탐색 후에 먹을 수 있는 물고기가 없다면 지금까지 이동한 거리를 출력하고 탐색을 종료한다.

 

1. 사용자 입력 및 변수 설정

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)] # 바다
d = [(-1, 0), (0, -1), (1, 0), (0, 1)]
shark = list() # 현재 상어 위치
shark_size = 2 # 현재 상어 크기
eaten = 0 # 상어가 먹는 물고기 수 (크기가 커지면 리셋)

# 상어 위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0 # 상어 위치를 공백으로 설정
            shark = [i, j]; break # 상어 위치 저장

n과 바다에 물고기, 상어 정보를 입력 받는다. 물고기는 1~6 숫자, 상어는 9, 공백은 0으로 입력된다.

shark에는 현재 아기 상어의 위치가 저장될 것이고, shark_size는 2로 초기화된다. eaten은 상어가 먹은 물고기 수인데 shark_size만큼 먹으면 shark_size는 1 커지고, eaten은 0으로 초기화된다.

바다를 탐색하면서 상어 위치를 찾으면 해당 위치를 공백(0)으로 설정하고 shark에 위치를 저장하고 반복문을 종료한다. (사실 N의 크기가 아주 크다면 이중 반복문을 모두 빠져나가서 좀 더 시간을 줄여야하지만 이 문제에서는 시간에 크게 영향을 미칠 것 같지는 않아서 단순하게 구현했다)

 

2. 탐색

answer = 0 # 총 이동 시간
while True:
    time = bfs(*shark) # 현재 위치에서 먹은 물고기 위치까지의 이동 시간
    if time is None: # 먹을 수 있는 물고기가 없다면 None을 반환하는 bfs() 함수
        print(answer) # 지금까지 이동한 시간 출력 후 종료
        break
    else: answer += time # 이동 시간 누적

 

bfs() 함수는 다음과 같은 역할을 할 것이다.

• 매개 변수로 입력 받은 상어의 위치에서 먹을 수 있는 물고기 중 가장 가까운 물고기까지의 이동 시간을 반환한다
• 만약 먹을 수 있는 물고기가 하나도 없다면 None을 반환한다
• 상어가 물고기를 먹고 크기가 커지거나 현재 상어 위치가 변경되는 작업을 수행한다

위 역할이 잘 구현되었다고 했을 때 위 코드는 상어가 이동할 수 있는 동안 이동한 시간을 출력하고 종료하는 부분이다.

 

3. 상어의 상태를 관리하는 함수

# x, y 좌표의 물고기 잡아 먹고 상어 이동
def eat_fish(x, y):
    global eaten, shark_size, shark
    eaten += 1 # 물고기 먹은 것 기록
    if shark_size == eaten: # 상어 크기 만큼 먹으면
        shark_size += 1 # 상어 크기 1 커지고
        eaten = 0 # 먹은 기록은 0으로 초기화
    graph[x][y] = 0 # 물고기가 있던 위치 공백으로 변경
    shark = [x, y] # 물고기가 있던 위치로 상어 위치 변경

eat_fish() 함수는 상어가 먹을 수 있는 물고기를 발견했을 때 물고기를 먹고 상어의 크기가 커지고, 상어의 위치를 이동하는 동작을 수행하는 함수이다.

이 함수는 bfs() 함수 내에서 사용될 것이다.

 

4. bfs() 함수 작성

def bfs(x, y):
    global shark
    visited = [[False] * n for _ in range(n)]
    fishes = [] # [이동 시간, 행, 열] 저장
    visited[x][y] = True # 현재 상어 위치 방문 처리
    q = deque([(x, y, 0)]) # 상어의 이동 (x, y)까지 0초 소모됨

    while q:
        if 현재 위치까지의 이동 시간이 먹을 수 있는 물고기까지의 이동 시간보다 길다면:
            먹을 수 있는 물고기 중 가장 가까운 물고기 먹음
            return 먹을 수 있는 물고기까지의 거리
        if 물고기가 먹을 수 있는 크기라면:
        	이동 시간, 물고기 위치 저장
        for i in range(4):
            nx, ny = 다음 위치(상, 하, 좌, 우)
            if 다음 이동 위치가 상어보다 작거나 같고, 아직 방문하지 않았다면 이동 가능:
                방문 처리
                방문 큐에 추가
    if fishes:
    	먹을 수 있는 물고기가 있다면 먹는다
        return 이동 시간
    else: return None

설명을 위해 코드 형식으로 작성해보았다.

기본적으로 bfs의 기본 틀을 따른다.

거리가 같은 물고기 중에서 가장 우선순위가 높은 물고기를 선택해야한다. 나는 이 부분에서 Heap을 사용한 우선순위 큐를 사용했다.

while문 밑의 첫 번째 if문에서 "먹을 수 있는 물고기 중 가장 가까운 물고기 먹음"이라는 부분이 heap에서 가장 우선순위가 높은 물고기를 pop 한 부분이 된다.

여기서 우선순위는 물고기까지의 시간 -> 행 -> 열 순이기 때문에 Heap에 [시간, 행, 열] 쌍으로 넣었다.

물고기를 먹는 부분은 앞서 설명한 eat_fish() 함수에서 수행한다.

전체 bfs() 함수 코드는 다음과 같다.

def bfs(x, y):
    global shark
    visited = [[False] * n for _ in range(n)]
    fishes = [] # 시간, 행, 열 순으로 저장
    visited[x][y] = True
    q = deque([(x, y, 0)])

    while q:
        cx, cy, t = q.popleft()
        if fishes and t > fishes[0][0]: # 물고기 목록 중에 조건에 맞는 물고기 선택
            second, r, c = heapq.heappop(fishes)
            eat_fish(r, c)
            return second
        if 0 < graph[cx][cy] < shark_size: # 먹을 수 있는 물고기 목록에 추가
            heapq.heappush(fishes, (t, cx, cy))
        for i in range(4):
            nx, ny = cx + d[i][0], cy + d[i][1]
            if nx in range(n) and ny in range(n) and graph[nx][ny] <= shark_size and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny, t + 1))
    if fishes:
        second, r, c = fishes[0]
        eat_fish(r, c)
        return second
    else: return None

위에서 설명한 것과 같은 구조이기 때문에 둘을 비교하면서 확인하면 어떤 식으로 동작하는지 알 수 있을 거라 기대한다.

 

전체 코드

from collections import deque
import heapq

# x, y 좌표의 물고기 잡아 먹고 상어 이동
def eat_fish(x, y):
    global eaten, shark_size, shark
    eaten += 1
    if shark_size == eaten:
        shark_size += 1
        eaten = 0
    graph[x][y] = 0
    shark = [x, y]

def bfs(x, y):
    global shark
    visited = [[False] * n for _ in range(n)]
    fishes = [] # 시간, 행, 열 순으로 저장
    visited[x][y] = True
    q = deque([(x, y, 0)])

    while q:
        cx, cy, t = q.popleft()
        if fishes and t > fishes[0][0]: # 물고기 목록 중에 조건에 맞는 물고기 선택
            second, r, c = heapq.heappop(fishes)
            eat_fish(r, c)
            return second
        if 0 < graph[cx][cy] < shark_size: # 먹을 수 있는 물고기 목록에 추가
            heapq.heappush(fishes, (t, cx, cy))
        for i in range(4):
            nx, ny = cx + d[i][0], cy + d[i][1]
            if nx in range(n) and ny in range(n) and graph[nx][ny] <= shark_size and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny, t + 1))
    if fishes:
        second, r, c = fishes[0]
        eat_fish(r, c)
        return second
    else: return None

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
d = [(-1, 0), (0, -1), (1, 0), (0, 1)]
shark = list()
shark_size = 2
eaten = 0
# 상어 위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0
            shark = [i, j]; break

answer = 0
while True:
    time = bfs(*shark)
    if time is None:
        print(answer)
        break
    else: answer += time

 

채점 결과