BOJ - 아기 상어 16236번 (python)

❓ 문제 - 백준 아기 상어 16236번 - python 풀이법

출처 

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

16236번: 아기 상어

 

 

📝 문제해결법

1. 이 문제는 BFS + 구현으로 풀었다.

• 공간에 대한 정보를 입력받으면서 아기 상어가 존재하는 행,열을 저장하고, 처음에 아기상어가 존재하는 공간의 값을 0으로 바꿔준다.
• 현재 아기 상어가 존재하는 행과 열에 대해서 BFS를 돌아서 현재 자신보다 크기가 작은 물고기가 있는지 탐색하고, 존재한다면 가장 가까운 애들부터 먹는다. (이때, 이동 거리를 answer에 더해줌) 먹으러 갔을 때 위치를 현재위치로 변경한다.
• 먹었을 때 해당 공간의 물고기는 없애주고, eat 을 증가시켜준다. (eat은 아기 상어가 먹은 물고기) 만약 아기상어가 먹은 물고기의 수(eat)과 아기상어의 현재 크기가 같다면 아기 상어의 크기를 1 증가시켜고 eat은 0으로 초기화 해준다.
• 계속 크기가 자신보다 작은 물고기를 먹으러 다니면서, 만약 현재 크기가 자신보다 작은 물고기를 더이상 먹을 수 없다면 break로 while문을 빠져와서 answer을 출력한다.

2. BFS

• fish 리스트로 현재 아기 상어가 먹을 수 있는 물고기의 행,열 정보와 그 물고기까지의 이동 거리를 저장한다.
• 현재 위치에서 4방향으로 탐색해서 , 범위를 넘지 않고 만약 방문되지 않은 곳에 물고기가 존재하는데 물고기의 크기가 아기 상어의 크기보다 작다면 fish 리스트에 append 해주며, 물고기 탐색 queue에 nx, ny를 append 해준다.
• 그리고 탐색하는 공간이 빈칸(0) 이거나, 현재 아기 상어의 크기와 동일한 물고기가 존재한다면 아기상어가 지나갈 수 있기 때문에 탐색 queue에 nx, ny를 append 해준다.
• 만약 먹을 수 있는 물고기가 존재(fish 리스트의 길이가 1이상) 이라면, sort를 통해 (최단 거리의 물고기 - 행이 가장 작은 위치 - 열이 가장 작은 위치) 현재 위치에서 가장 먹을 수 있는 최단 거리의 물고기 정보를 return 해준다.

 

💻 소스코드

# 아기 상어 - BOJ 16236
# BFS + 구현
from collections import deque
n = int(input())
s_x, s_y = -1, -1
s_level, eat = 2, 0
graph = []

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

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(n):
        if data[j] == 9:
            s_x, s_y = i, j


graph[s_x][s_y] = 0

def bfs(s_x, s_y, s_level):
    visited = [[False]*n for _ in range(n)]
    q = deque()
    q.append((s_x, s_y, 0))
    visited[s_x][s_y] = True
    fish = []
    while q:
        x, y, count = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] != 0 and graph[nx][ny] < s_level:
                    fish.append((count+1, nx, ny))
                    q.append((nx, ny, count+1))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 0 or graph[nx][ny] == s_level:
                    visited[nx][ny] = True
                    q.append((nx, ny, count+1))

    fish.sort()
    if fish:
        return [fish[0][1], fish[0][2], fish[0][0]]
    else:
        return []

answer = 0

while True:
    fish_eat = bfs(s_x, s_y, s_level)
    if fish_eat:
        x, y, move = fish_eat
        graph[x][y] = 0
        eat += 1
        answer += move
        if eat == s_level:
            s_level += 1
            eat = 0
        s_x, s_y = x, y
    else:
        break

print(answer)