[BFS] 백준#16236: 아기 상어/Python

📝 문제

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

16236번: 아기 상어

💡 접근법

1) 알고리즘 및 자료구조

BFS 알고리즘과 큐(Queue) 자료구조를 활용하여 문제를 해결하였습니다. 상어가 새로운 좌표로 이동하면, 탐색 시작점 역시 해당 새로운 좌표로 이동한 것과 같습니다. 따라서 초기 상어의 위치를 큐에 넣고 탐색할 때마다 꺼내며, 새로운 좌표로 이동할 때마다 큐에 넣는 과정을 반복하면 됩니다.

2) 문제풀이 전략

상어는 가능한 최대한 많은 물고기를 먹어야 합니다. 즉, 잡아먹을 수 있는(=탐색 가능한) 모든 물고기의 위치를 방문해야 하죠. 물고기를 잡아먹으러 갈 때마다 소요되는 시간을 1씩 증가시켜 줘야 합니다. 물고기를 잡아먹을 때마다 해당 위치의 좌표와 방문하는 데 필요한 총 거리(=문제에서는 시간)를 저장할 리스트가 필요합니다. 특히, 같은 거리 내 물고기가 여러 마리 있을 경우가 있기 때문에, '거리-행-열' 순서대로 각각의 값이 작을수록 높은 우선순위를 매기기 위해 리스트 정렬이 필요합니다. 이 리스트를 활용하여 최대한 많은 물고기를 잡아먹을 때까지 상어의 크기 증대를 결정하고, 해당 지점에서 다시 BFS를 수행합니다.

💻 코드

1) 전체 코드

# 문제 원본: https://www.acmicpc.net/problem/16236
# 개인 해설: https://heytech.tistory.com/375
import sys; input = sys.stdin.readline
from collections import deque

# 잡아먹을 수 있는 물고기 탐색 함수
def bfs(x, y):
    global shark_size
    visited = [[False]*N for _ in range(N)]
    fish = [] # 물고기 잡아먹을 시 소요거리 및 좌표정보 저장용 리스트
    q = deque()
    q.append((0, x, y))
    while q:
        dist, x, y = q.popleft()
        visited[x][y] = True
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                visited[nx][ny] = True
                # 잡아먹을 수 있는 물고기 존재하는 경우
                if 1 <= graph[nx][ny] <= 6 and graph[nx][ny] < shark_size:
                    q.append((dist + 1, nx, ny))
                    fish.append((dist + 1, nx, ny)) # 물고기 잡아먹을 때만 정보 저장
                # 빈 공간이거나 상어와 같은 크기의 물고기가 존재하는 경우
                elif graph[nx][ny] == 0 or shark_size == graph[nx][ny]:
                    q.append((dist+1, nx, ny))

    if fish:
        # 같은 거리에 여러마리의 물고기가 있을 경우를 대비하기 위해 리스트 정렬
        # '거리-행-열' 순으로 각각의 값이 작을수록 잡아먹는 데 우선순위가 높은 물고기
        return sorted(fish)[0]
    else:
        return False

# 최종정답 연산 함수
def solve(x, y):
    global answer
    global shark_size
    eat = 0
    # 잡아먹을 수 있는 물고기를 모두 잡아먹을 때까지 무한반복
    while True:
        fish = bfs(x, y)
        # 잡아먹은 물고기가 있는 경우
        if fish:
            dist, x_shark, y_shark = fish
            graph[x_shark][y_shark] = 0
            eat += 1
            answer += dist
            if eat == shark_size:
                shark_size += 1
                eat = 0
            x = x_shark
            y = y_shark
        else:
            break

# 물고기 존재여부 확인용 함수
def exist_fish():
    for i in range(N):
        for j in range(N):
            if 1 <= graph[i][j] <= 6:
                return True
    return False

# 상어 좌표 반환용 함수
def find_shark():
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 9:
                return i, j

# 메인함수
if __name__ == '__main__':
    N = int(input())
    graph = [list(map(int, input().split())) for _ in range(N)]
    if not exist_fish():
        print(0)
        exit(0)
    else:
        shark_size = 2
        d = [(-1, 0), (0, -1), (0, 1), (1, 0)]
        x, y = find_shark()
        graph[x][y] = 0
        answer = 0
        solve(x, y)
        print(answer)

2) 해설

(1) 패키지 import

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

from collections import deque

큐(queue) 자료구조를 사용하기 위해 deque 모듈을 불러왔습니다.

(2) 물고기 존재여부 확인 함수

def exist_fish():
    for i in range(N):
        for j in range(N):
            if 1 <= graph[i][j] <= 6:
                return True
    return False

물고기가 존재하는지 확인하는 코드입니다. 물고기가 전혀 없다면 메인 함수에서 \(0\)을 출력하고 프로그램을 즉시 종료합니다.

(3) 상어 위치 확인 함수

# 상어 좌표 반환용 함수
def find_shark():
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 9:
                return i, j

상어가 위치한 좌표를 반환하는 함수입니다.

(4) 메인 함수

# 메인함수
if __name__ == '__main__':
    N = int(input())
    graph = [list(map(int, input().split())) for _ in range(N)]
    if not exist_fish():
        print(0)
        exit(0)
    else:
        shark_size = 2
        d = [(-1, 0), (0, -1), (0, 1), (1, 0)]
        x, y = find_shark()
        graph[x][y] = 0
        answer = 0
        solve(x, y)
        print(answer)

(5) BFS 함수

# 잡아먹을 수 있는 물고기 탐색 함수
def bfs(x, y):
    global shark_size
    visited = [[False]*N for _ in range(N)]
    fish = [] # 물고기 잡아먹을 시 소요거리 및 좌표정보 저장용 리스트
    q = deque()
    q.append((0, x, y))
    while q:
        dist, x, y = q.popleft()
        visited[x][y] = True
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                visited[nx][ny] = True
                # 잡아먹을 수 있는 물고기 존재하는 경우
                if 1 <= graph[nx][ny] <= 6 and graph[nx][ny] < shark_size:
                    q.append((dist + 1, nx, ny))
                    fish.append((dist + 1, nx, ny)) # 물고기 잡아먹을 때만 정보 저장
                # 빈 공간이거나 상어와 같은 크기의 물고기가 존재하는 경우
                elif graph[nx][ny] == 0 or shark_size == graph[nx][ny]:
                    q.append((dist+1, nx, ny))

    if fish:
        # 같은 거리에 여러마리의 물고기가 있을 경우를 대비하기 위해 리스트 정렬
        # '거리-행-열' 순으로 각각의 값이 작을수록 잡아먹는 데 우선순위가 높은 물고기
        return sorted(fish)[0]
    else:
        return False

5번째 라인

• 물고기를 잡아 먹을 때까지 소요된 시간, 잡아먹은 물고기의 위치 정보를 저장하는 리스트

17~19번째 라인

• 상어가 잡아먹을 수 있는 물고기가 있는 경우, \(5\)번째 라인에서 초기화한 리스트에 거리, 좌표 정보 삽입

20~22번째 라인

• 이동할 공간이 빈 공간이거나 상어 사이즈와 같은 물고기가 존재하는 경우 이동 가능

24~27번째 라인

• '거리-행-열' 순서대로 각각의 값이 작을수록 잡아먹어야 하는 우선순위가 높기 때문에, sorted 메서드를 활용하여 리스트 정렬

28~29번째 라인

• 잡아먹을 물고기가 없는 경우 False 리턴

(6) 정답 연산 함수

# 최종정답 연산 함수
def solve(x, y):
    global answer
    global shark_size
    eat = 0
    # 잡아먹을 수 있는 물고기를 모두 잡아먹을 때까지 무한반복
    while True:
        fish = bfs(x, y)
        # 잡아먹은 물고기가 있는 경우
        if fish:
            dist, x_shark, y_shark = fish
            graph[x_shark][y_shark] = 0
            eat += 1
            answer += dist
            if eat == shark_size:
                shark_size += 1
                eat = 0
            x = x_shark
            y = y_shark
        else:
            break

잡아먹은 물고기가 없을 때까지 다음 로직을 무한반복하는 함수이자 최종 정답인 총 소요시간을 합산하는 함수입니다. BFS 함수로부터 잡아먹은 물고기 정보를 전달받은 경우, 물고기를 잡아먹은 횟수를 증가시키고 이를 상어 크기와 비교하여 상어 크기 증대를 결정합니다. 최종 정답인 answer 변수에 가능한 최대한의 물고기를 모두 잡아먹는 데 필요한 시간을 합산합니다.

✅ 채점 결과

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_16236.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 풀이에 사용한 BFS 알고리즘과 큐 자료구조에 대한 자세한 설명은 아래 포스팅을 참고해 주세요.

https://heytech.tistory.com/56

[알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)

https://heytech.tistory.com/54

큐(Queue) 자료구조 이해(+ Python)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.