[Python] 백준 16236 아기 상어

1. 문제 링크

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

16236번: 아기 상어

---

2. 문제 요약

• 아기 상어가 물고기를 먹으러 가는데 걸리는 최단 거리 구하기

아기 상어 문제 요약 

---

3. 아이디어 정리

1. bfs로 현재 상어 위치에서 갈 수 있는 최단 거리를 찾는다. ⇒ bfs
   • 예외처리 필요: 큰 상어는 못 지나간다.
2. 1 결과를 이용하여 가장 가까운 물고기 위치를 얻는다.
   • 예외 처리: 아기 상어보다 작은 물고기만 먹을 수 있다.
3. 2에서 진행한 결과가 있는 경우 아기 상어 위치와 크기를 갱신 후 1번 다시 진행, 2 결과가 없는 경우 break(엄마한테 요청)

---

4. 문제 풀이

4-1. 내 풀이

import sys
from collections import deque

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(now_pos, now_size):
    """
    현재 상어 위치에서 갈 수 있는 최단 거리를 찾는다.
    """
    dq = deque()
    dq.append(now_pos)
    visit[now_pos[0]][now_pos[1]] = 1
    while dq:
        x, y = dq.popleft()
        for d in range(4):
            nx = dx[d] + x
            ny = dy[d] + y
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if visit[nx][ny] != 0:
                continue
            if graph[nx][ny] > now_size:  # 큰 물고기는 못지나감
                continue
            visit[nx][ny] = visit[x][y] + 1
            dq.append((nx, ny))

def get_min_dist(now_size):
    """
    최단 거리에 있는 물고기를 찾아 거리를 얻는다.
    :param now_size: 현재 상어 크기
    :return: 상어가 이동할 좌표, 상어가 이동할 최단 거리
    """
    x, y = 0, 0
    min_dist = int(1e9)
    for i in range(n):
        for j in range(n):
            # 방문 했고, 물고기가 존재, 상어 크기보다 작은 경우 방문
            if visit[i][j] != 0 and graph[i][j] > 0 and graph[i][j] < now_size:
                if min_dist > visit[i][j] - 1:   # 지금까지 가장 가까운 거리인 경우 저장
                    min_dist = visit[i][j] - 1
                    x = i
                    y = j
    return (x, y, min_dist)

n = int(sys.stdin.readline())   # 공간의 크기
graph = [[] for _ in range(n)]
# visit = [[0] * n for _ in range(n)]

ans = 0
now_size = 2
now_ate = 0
now_pos = (0, 0)
for i in range(n):
    arr = list(map(int, sys.stdin.readline().split()))
    now = [(i, j) for j, a in enumerate(arr) if a == 9]
    if now: now_pos = now[0]
    graph[i] = arr
graph[now_pos[0]][now_pos[1]] = 0  # 상어의 위치는 0으로 설정

while True:
    # 1. bfs로 현재 상어 위치에서 갈 수 있는 최단 거리를 찾는다.
    visit = [[0] * n for _ in range(n)]
    bfs(now_pos, now_size)
    # 2. 최단 거리에 있는 물고기를 찾아 거리를 얻는다.
    x, y, dist = get_min_dist(now_size)  # 상어가 이동한 위치, 상어 이동 거리
    if dist != int(1e9):  # 상어 이동 가능한 경우
        ans += dist
        now_pos = (x, y)            # 상어 위치 변경
        now_ate += 1                # 현재까지 먹은 물고기 더하기
        # 상어 사이즈만큼 먹은 경우 상어 사이즈 증가
        if now_ate == now_size:
            now_size += 1
            now_ate = 0
        graph[x][y] = 0             # 현재 상어의 위치 0으로 변경
    else:               # 상어 이동 불가능한 경우
        break
print(ans)

 

---

5. 결론

• 최단 거리를 구하는 bfs 문제 but 예외 처리할 것이 많았던 문제이다. (상어 크기🦈 , 물고기 크기 🐠 등등)