[baekjoon] 백준 16236번(파이썬): 아기 상어

문제

16236번: 아기 상어

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 아기 상어가 먹을 수 있는 물고기가 없을 때까지 반복한다.

- 아기 상어가 현재 이동할 수 있는 모든 곳을 탐색하고 이동한 곳에 아기 상어보다 크기가 작은 물고기가 있다면 힙에 추가한다.

- 문제를 보면 위, 왼쪽 물고기부터 먹어야 하는 우선순위가 있다. 따라서 heapq 우선순위 큐를 통해 물고기를 먹는다.

- 아기 상어의 크기와 먹은 물고기의 양이 같다면 아기 상어의 크기를 1 키운다.

- 위 과정을 반복하고 먹을 물고기가 없다면 반복을 멈추고 총 이동 시간을 출력한다. 

코드

import sys
from collections import deque
import heapq


# bfs 탐색
def bfs(x, y):
    global res, eat, size
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 아기 상어가 먹을 수 있는 물고기가 없을 때까지 반복
    while True:
        queue = deque([[x, y, 0]]) # 아기 상어의 x좌표, y좌표, 이동 시간
        visited = [[False] * n for _ in range(n)] # 탐색 여부
        visited[x][y] = True # 현재 아기 상어의 위치
        heap = [] # 아기 상어가 먹을 수 있는 물고기
        flag = n ** 2 # 아기 상어의 최소 이동 시간

        # 아기 상어가 갈 수 있는 모든 곳을 탐색
        while queue:
            a, b, cnt = queue.popleft()

            # 아기 상어의 최소 이동 시간보다 많은 시간이 필요한 곳부터는 탐색을 멈춘다.
            if cnt > flag:
                break

            # 상/하/좌/우 탐색
            for i in range(4):
                nx = a + dx[i]
                ny = b + dy[i]

                # 공간 안에 있고 탐색하지 않았고 아기 상어의 크기보다 작거나 같은 물고기 이거나 공간이라면
                if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False and graph[nx][ny] <= size:
                    # 아기 상어보다 작은 물고기 이고 공간이 아니라면
                    if graph[nx][ny] < size and graph[nx][ny] != 0:
                        heapq.heappush(heap, (nx, ny, cnt + 1)) # 먹을 수 있는 물고기를 힙에 추가
                        flag = cnt # 아기 상어의 최소 이동시간을 초기화

                    queue.append([nx, ny, cnt + 1])
                    visited[nx][ny] = True

        # 아기 상어가 먹을 수 있는 물고기가 있다면
        if len(heap) > 0:
            # 위, 왼쪽에 물고기 부터 우선적으로 먹어야 하기때문에 heapq 를 사용
            x, y, move = heapq.heappop(heap)
            res += move # 이동 시간을 더해준다.
            eat += 1 # 물고기를 먹는다.
            graph[x][y] = 0 # 먹은 물고기의 자리는 0으로 초기화

            # 먹은 물고기의 수가 아기 상어의 크기와 같다면
            # 아기 상어의 크기를 올려준다.
            if eat == size:
                size += 1
                eat = 0

        # 먹을 물고기가 없으면 탐색을 멈춰준다.
        else:
            break


n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
size = 2 # 아기 상어의 크기
res = 0 # 최소 이동 시간
eat = 0 # 먹은 물고기 수

# 아기 상어의 위치를 찾는다.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0 # 아기 상어의 위치를 0으로 초기화
            bfs(i, j)
            break
print(res)

 

실패한 코드(틀렸습니다.)

import sys
from collections import deque
import heapq


# bfs 탐색
def bfs(x, y):
    global res, eat, size
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 아기 상어가 먹을 수 있는 물고기가 없을 때까지 반복
    while True:
        queue = deque([[x, y, 0]])
        visited = [[False] * n for _ in range(n)] # 탐색 여부
        visited[x][y] = True # 현재 아기 상어의 위치
        heap = [] # 아기 상어가 먹을 수 있는 물고기
        flag = n ** 2 # 아기 상어의 최소 이동 시간

        # 아기 상어가 갈 수 있는 모든 곳을 탐색
        while queue:
            a, b, cnt = queue.popleft()

            # 아기 상어의 최소 이동 시간보다 많은 시간이 필요한 곳부터는 탐색을 멈춘다.
            if cnt > flag:
                break

            # 상/하/좌/우 탐색
            for i in range(4):
                nx = a + dx[i]
                ny = b + dy[i]

                # 공간 안에 있고 탐색하지 않았으면
                if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False:
                    # 아기 상어보다 작은 물고기이고 공간이 아니라면
                    if graph[nx][ny] < size and graph[nx][ny] != 0:
                        heapq.heappush(heap, (nx, ny, cnt + 1)) # 먹을 수 있는 물고기를 힙에 추가
                        flag = cnt # 아기 상어의 최소 이동시간을 초기화

                    queue.append([nx, ny, cnt + 1])
                    visited[nx][ny] = True

        # 아기 상어가 먹을 수 있는 물고기가 있다면
        if len(heap) > 0:
            # 위, 왼쪽에 물고기 부터 우선적으로 먹어야 하기때문에 heapq 를 사용
            x, y, move = heapq.heappop(heap)
            res += move # 이동 시간을 더해준다.
            eat += 1 # 물고기를 먹는다.
            graph[x][y] = 0 # 먹은 물고기의 자리는 0으로 초기화

            # 먹은 물고기의 수가 아기 상어의 크기와 같다면
            # 아기 상어의 크기를 올려준다.
            if eat == size:
                size += 1
                eat = 0

        # 먹을 물고기가 없으면 탐색을 멈춰준다.
        else:
            break


n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
size = 2 # 아기 상어의 크기
res = 0 # 최소 이동 시간
eat = 0 # 먹은 물고기 수

# 아기 상어의 위치를 찾는다.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0 # 아기 상어의 위치를 0으로 초기화
            bfs(i, j)
            break
print(res)

실패한 코드를 보게 되면 아기 상어가 먹을 수 있는 물고기를 탐색할 때 아기 상어보다 작은 물고기만을 찾아 탐색한 것을 확인할 수 있다. 문제에서 아기 상어와 크기가 같은 물고기여도 그 공간을 지날 수 있으므로 아기 상어와 크기가 같은 물고기라면 그곳으로 이동 후 탐색할 수 있게 조건을 고쳐주어 코드를 다시 작성하여 문제를 수행했다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법