[탐색/BFS] 백준 16236 아기 상어 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

16236번: 아기 상어

 

 

2. 문제 풀이

 아기 상어가 먹을 수 있는 먹잇감을 모두 먹는 데에 걸리는 시간을 구하는 문제입니다. 자신보다 작은 물고기만 먹을 수 있고, 크기 2부터 시작합니다. 자신보다 큰 물고기는 통과할 수 없으며, 자신과 동일한 크기면 통과할 수 있습니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS탐색을 이용해서 '현재 위치'에서 자신이 먹을 수 있는 물고기를 탐색합니다. 동일한 거리에 있을 경우에는 '위', '왼쪽'에 있는 물고기를 먼저 먹습니다.

 

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

#입력
N = int(input())
sea = []  # 그래프
startX, startY = 0, 0 # 아기상어 위치
for i in range(N):
    lst = list(map(int, input().split()))
    for j in range(N):
        if lst[j] == 9:
            lst[j] = 0  # 크기가 9인 물고기로 오인하지 않도록
            startX, startY = i, j  # 아기상어 위치
    sea.append(lst)

 물고기 위치를 입력받고, 아기 상어의 위치를 저장합니다. 아기 상어의 위치는 9로 입력되며, 크기가 9인 물고기로 오인하지 않도록 0으로 바꿔줍니다.

 

 

# BFS탐색
direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]  # 상하좌우
size = 2
move = 0
eat = 0

while True:
    visited = [[False] * N for _ in range(N)]  # 방문표시
    queue = deque([(startX, startY, 0)])  # 시작 위치
    visited[startX][startY] = True
    flag = 9999 # 먹을 수 있는 물고기 탐색여부
    fish = []  # 물고기 위치
    while queue:
        x, y, cnt = queue.popleft()
        if cnt > flag:
            break

        #상하좌우 탐색
        for dx, dy in direction:
            nx, ny = x+dx, y+dy
            # 범위를 벗어나지 않고, 자신이 지나갈 수 있는 미방문인 곳을 탐색
            if 0 <= nx < N and 0 <= ny < N and sea[nx][ny] <= size and not visited[nx][ny]:
                visited[nx][ny] = True  # 방문
                queue.append((nx, ny, cnt+1))
                # 자신보다 작은 물고기가 있으면 먹음
                if 0 < sea[nx][ny] < size:
                    fish.append((nx, ny, cnt+1))
                    flag = cnt  # 탐색완료

 아기 상어 위치에서 가장 가까운 먹잇감 위치를 BFS 탐색합니다. 자신보다 작은 먹잇감을 찾았으면, queue에 넣고 해당 위치에서 다시 BFS 탐색할 준비를 합니다.

 

 

    # 먹을 수 있는 물고기가 있으면 계속 탐색
    if fish:
        fish.sort() #위, 왼쪽 물고기 먼저 먹음
        x, y, dist = fish[0] #먹을 물고기 위치와 필요한 이동거리
        sea[x][y] = 0 #먹고나면 빈 칸
        move += dist

        # 먹은 물고기 횟수+1, 사이즈와 동일하다면 사이즈업
        eat += 1
        if eat == size:
            size += 1
            eat = 0
        startX, startY = x, y

    # 더이상 먹을 수 있는 물고기 없음
    else:
        break
print(move)

 print(move)를 제외하곤 while True 반복문 안입니다. BFS탐색에서 찾은 물고기 중 거리가 가장 짧은 물고기를 먹습니다. 거리가 같다면 가장 위, 왼쪽인 물고기를 먼저 먹습니다. (거리, 행, 열 순으로 오름차순 정렬)

 먹고 난 물고기칸은 빈 칸(0)이 되고, 해당 거리만큼 시간을 더해줍니다. (1초에 1칸 이동) 먹은 물고기 횟수를 +1 해주고, 사이즈와 동일해졌다면 사이즈를 올려줍니다. 이후 시작 지점을 먹은 물고기 칸(x, y)으로 갱신하고 BFS 탐색을 진행합니다.

 만약 더 이상 먹을 수 있는 물고기가 없다면 탐색을 종료합니다.

 

 

cf) Flag 오류

from collections import deque
import sys
input = sys.stdin.readline

#입력
N = int(input())
sea = []  # 그래프
startX, startY = 0, 0 # 아기상어 위치
for i in range(N):
    lst = list(map(int, input().split()))
    for j in range(N):
        if lst[j] == 9:
            lst[j] = 0  # 크기가 9인 물고기로 오인하지 않도록
            startX, startY = i, j  # 아기상어 위치
    sea.append(lst)

# BFS탐색
direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]  # 상하좌우
size = 2
move = 0
eat = 0

while True:
    visited = [[False] * N for _ in range(N)]  # 방문표시
    queue = deque([(startX, startY, 0)])  # 시작 위치
    visited[startX][startY] = True
    flag = False # 먹을 수 있는 물고기 탐색여부
    fish = []  # 물고기 위치
    while queue:
        x, y, cnt = queue.popleft()
        if flag:
            break

        #상하좌우 탐색
        for dx, dy in direction:
            nx, ny = x+dx, y+dy
            # 범위를 벗어나지 않고, 자신이 지나갈 수 있는 미방문인 곳을 탐색
            if 0 <= nx < N and 0 <= ny < N and sea[nx][ny] <= size and not visited[nx][ny]:
                visited[nx][ny] = True  # 방문
                queue.append((nx, ny, cnt+1))
                # 자신보다 작은 물고기가 있으면 먹음
                if 0 < sea[nx][ny] < size:
                    fish.append((nx, ny, cnt+1))
                    flag = True  # 탐색완료

    # 먹을 수 있는 물고기가 있으면 계속 탐색
    if fish:
        fish.sort() #위, 왼쪽 물고기 먼저 먹음
        x, y, dist = fish[0] #먹을 물고기 위치와 필요한 이동거리
        sea[x][y] = 0 #먹고나면 빈 칸
        move += dist

        # 먹은 물고기 횟수+1, 사이즈와 동일하다면 사이즈업
        eat += 1
        if eat == size:
            size += 1
            eat = 0
        startX, startY = x, y

    # 더이상 먹을 수 있는 물고기 없음
    else:
        break
print(move)

 위 정답코드와 달리, flag를 bool 변수로 두었습니다. break 조건을 cnt > flag로 두지 않으면, 거리가 같은 다른 물고기를 탐색하지 못합니다.

 

5
3 3 2 4 3
1 4 5 3 1
1 4 3 3 2
4 3 2 3 1
3 3 1 3 9

정답: 31
출력: 34

 위 예제를 살펴보면 12초에서 잘못된 선택을 합니다.

 

 본래라면 상단이고 왼쪽인 물고리를 먹어야 합니다. (아기 상어의 위치를 9로 표시)

 

 하지만, 위 코드는 12초에서 오른쪽 상단의 물고기를 먹습니다. (먹은 물고기 자리를 -1로 표시)

 먹잇감만 찾으면, 1~3번의 탐색 뒤에 발견될 동일한 거리의 먹잇감이 무시되기 때문입니다. 따라서 cnt > flag로 동일 거리의 먹잇감 탐색이 이루어지도록 조정하면, 정답 코드가 됩니다.