Note
2D 그리드에서 BFS를 활용하여 목표 지점으로부터 모든 지점까지의 최단 거리를 구하는 문제입니다.
문제 링크
문제 요약
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하세요. 오직 가로와 세로로만 움직일 수 있습니다.
- 입력: 지도의 크기 n, m과 지도 정보 (0: 갈 수 없는 땅, 1: 갈 수 있는 땅, 2: 목표지점)
- 출력: 각 지점에서 목표지점까지의 거리
- 원래 갈 수 없는 땅: 0
- 원래 갈 수 있는 땅인데 도달할 수 없음: -1
핵심 아이디어
목표지점에서 역방향 BFS
일반적으로는 시작점에서 목표지점까지의 거리를 구하지만, 이 문제는 목표지점에서 모든 지점까지의 거리를 구해야 합니다.
- 목표지점(2)을 시작점으로 설정
- BFS를 통해 모든 도달 가능한 지점까지의 거리 계산
- 원래 갈 수 있는 땅(1)인데 도달할 수 없는 곳은 -1로 표시
알고리즘 설계
1. 목표지점 찾기 및 초기화
queue = deque([])
# 목표지점 찾기
for y in range(n):
for x in range(m):
if grid[y][x] == 2:
queue.append((y, x))
break2. BFS 탐색
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
while queue:
v = queue.popleft()
value = path[v[0]][v[1]]
for d in offset:
dy = v[0] + d[0]
dx = v[1] + d[1]
if 0 <= dy < n and 0 <= dx < m:
if path[dy][dx] == 0 and grid[dy][dx] == 1:
queue.append((dy, dx))
path[dy][dx] = value + 13. 도달 불가능한 곳 처리
for y in range(n):
for x in range(m):
if grid[y][x] == 1 and path[y][x] == 0:
path[y][x] = -1전체 코드
import sys
from collections import deque
readline = sys.stdin.readline
n, m = map(int, readline().split())
# 지도 입력
grid: list[list[int]] = []
for _ in range(n):
row = list(map(int, readline().split()))
grid.append(row)
path: list[list[int]] = [[0 for _ in range(m)] for _ in range(n)]
queue = deque([])
# 시작 지점 입력
for y in range(n):
for x in range(m):
if grid[y][x] == 2:
queue.append((y, x))
break
# 출발지 임의로 -1로 하기.
# path[y][x] = -1
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상하좌우
while queue:
v = queue.popleft()
value = path[v[0]][v[1]]
for d in offset:
dy = v[0] + d[0]
dx = v[1] + d[1]
if 0 <= dy and dy < n and 0 <= dx and dx < m:
if path[dy][dx] == 0 and grid[dy][dx] == 1:
queue.append((dy, dx))
path[dy][dx] = value + 1
# 원래 갈 수 있는 땅인데 도달할 수 없다면 -1로 변경.
for y in range(n):
for x in range(m):
if grid[y][x] == 1 and path[y][x] == 0:
path[y][x] = -1
for row in path:
print(' '.join(map(str, row)))코드 설명
1. 입력 처리
n, m = map(int, readline().split())
grid: list[list[int]] = []
for _ in range(n):
row = list(map(int, readline().split()))
grid.append(row)
path: list[list[int]] = [[0 for _ in range(m)] for _ in range(n)]grid: 원본 지도 정보path: 거리 정보를 저장할 배열 (초기값 0)
2. 목표지점 찾기
queue = deque([])
for y in range(n):
for x in range(m):
if grid[y][x] == 2:
queue.append((y, x))
break- 목표지점(2)을 찾아서 큐에 추가
- 문제에서 목표지점은 단 한 개라고 명시됨
3. BFS 탐색
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상하좌우
while queue:
v = queue.popleft()
value = path[v[0]][v[1]]
for d in offset:
dy = v[0] + d[0]
dx = v[1] + d[1]
if 0 <= dy < n and 0 <= dx < m:
if path[dy][dx] == 0 and grid[dy][dx] == 1:
queue.append((dy, dx))
path[dy][dx] = value + 1- 목표지점에서 시작하여 BFS 탐색
path[dy][dx] == 0: 아직 방문하지 않은 곳grid[dy][dx] == 1: 갈 수 있는 땅- 거리를
value + 1로 저장
4. 도달 불가능한 곳 처리
for y in range(n):
for x in range(m):
if grid[y][x] == 1 and path[y][x] == 0:
path[y][x] = -1- 원래 갈 수 있는 땅(1)인데 거리가 0인 곳은 도달할 수 없는 곳
- -1로 변경
시간 복잡도
-
시간 복잡도: O(N × M)
- 모든 칸을 한 번씩 방문
- 각 칸에서 상하좌우 확인은 상수 시간
-
공간 복잡도: O(N × M)
- 그리드 저장: O(N × M)
- 경로 배열: O(N × M)
- 큐: 최악의 경우 O(N × M)
풀이 포인트
1. 역방향 BFS
일반적인 BFS는 시작점에서 목표지점까지의 거리를 구하지만, 이 문제는 목표지점에서 모든 지점까지의 거리를 구해야 합니다. 목표지점을 시작점으로 설정하면 됩니다.
2. 두 개의 배열 사용
grid: 원본 지도 정보 (0, 1, 2)path: 거리 정보 (0: 미방문 또는 갈 수 없는 땅, 양수: 거리, -1: 도달 불가능)
3. 도달 불가능 판단
BFS가 끝난 후에도 grid[y][x] == 1이고 path[y][x] == 0인 곳은 목표지점에 도달할 수 없는 곳입니다.
관련 문제
- BFS (너비 우선 탐색) - 2D 그리드 BFS 이론
- BOJ 7576: 토마토 - 다중 시작점 BFS
- BOJ 2178: 미로 탐색 - 2D 그리드에서 최단 경로 찾기