코딩테스트

[BFS] 백준 17086. 아기 상어 2

말하는 감자에요 2025. 6. 13. 11:48
728x90
반응형

오늘 다룰 문제는 BFS(너비 우선 탐색)의 정석 같은 문제입니다.

 

특히 다수의 시작점에서 동시에 BFS를 수행하는 방식이 핵심이며, 최단 거리 문제에서 매우 자주 등장합니다.

 

한 칸마다 가장 가까운 아기 상어와의 거리를 구하는 문제이기 때문에, 모든 상어에서 동시에 퍼져나가며 각 칸의 최단 거리를 갱신해주는 전략이 유효합니다.

1. 문제: 백준 17086. 아기 상어 2

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

예제 입력 1

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1

2

예제 입력 2

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2

2

2. 문제 풀이

이 문제는 다음과 같이 풀 수 있습니다.

✔️ 접근 방법 요약

  • 아기 상어가 있는 모든 위치를 큐에 넣고 멀티 소스 BFS를 수행합니다.
  • BFS를 통해 빈 칸으로 이동하며, 각 칸에 가장 가까운 상어와의 거리를 계산합니다.
  • 최종적으로 계산된 거리 중에서 가장 큰 값을 출력하면 됩니다.

✔️ 핵심 아이디어: "멀티 소스 BFS"

보통 BFS는 한 지점에서 출발합니다. 그러나 이번 문제는 모든 상어의 위치에서 동시에 퍼져 나가는 것이 효율적입니다.

예를 들어 상어가 3마리 있다면, 이 3개의 좌표를 큐에 모두 넣고, 동시에 탐색을 시작하여 가장 가까운 상어로부터의 거리를 계산할 수 있습니다.

구현 코드

from collections import deque
def bfs(N, M, grid):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    queue = deque()
    visited = [[False] * M for _ in range(N)]
    max_dist = 0

    for i in range(N):
        for j in range(M):
            if grid[i][j] == 1:
                queue.append((i, j, 0))
                visited[i][j] = True

    while queue:
        cur_x, cur_y, cur_d = queue.popleft()

        for dx, dy in directions:
            next_x, next_y = cur_x + dx, cur_y + dy

            if 0 <= next_x < N and 0 <= next_y < M:
                if not visited[next_x][next_y]:
                    visited[next_x][next_y] = True
                    max_dist = max(max_dist, cur_d + 1)
                    queue.append((next_x, next_y, cur_d + 1))
    
    return max_dist

def main():
    N, M = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(N)]

    print(bfs(N, M, grid))

if __name__ == '__main__':
    main()

시간 복잡도

  • BFS는 각 칸을 최대 1번만 방문하므로,
  • 전체 시간 복잡도는 O(N × M)입니다.
  • N, M ≤ 50이므로 최대 2,500칸, 시간 제한 내에 충분히 통과 가능합니다.

3. 마무리

이 문제는 다음과 같은 점에서 BFS 연습에 매우 좋습니다:

  • 멀티 소스 BFS를 어떻게 쓰는지 체득할 수 있고,
  • 8방향 이동을 직접 구현해볼 수 있으며,
  • 거리 개념과 BFS의 조합이 자연스럽게 드러나는 문제입니다.

그래서 실버 2지만 충분히 쉬운 문제로 느껴질 수 있고, BFS 입문 또는 복습용 문제로 강력 추천드립니다.

읽어주셔서 감사합니다.

728x90
반응형