Note
2D 그리드에서 BFS를 활용하여 (1, 1)에서 (N, M)까지의 최단 경로를 구하는 문제입니다.
문제 링크
문제 요약
N×M 크기의 미로가 주어집니다. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하세요.
- 입력: 미로의 크기 N, M과 미로 정보 (1: 이동 가능, 0: 이동 불가)
- 출력: 지나야 하는 최소의 칸 수 (시작 위치와 도착 위치 포함)
핵심 아이디어
2D 그리드에서의 BFS
이 문제는 2차원 그리드에서 BFS를 사용하여 최단 경로를 찾는 전형적인 문제입니다.
- 시작 위치 (0, 0)에서 BFS 시작
- 상하좌우로 이동 가능한 칸을 탐색
- 각 칸에 도달하는 최소 칸 수를 저장
- 목표 위치 (N-1, M-1)에 도달하면 종료
거리 저장 방식
그리드에 직접 거리(칸 수)를 저장하는 방식을 사용합니다:
- 시작 위치: 1
- 다음 칸: 2
- 그 다음 칸: 3
- …
알고리즘 설계
1. 초기화
queue = deque([(0, 0)]) # 시작 위치2. BFS 탐색
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상, 하, 좌, 우
while queue:
v = queue.popleft()
y = v[0]
x = v[1]
value = grid[y][x]
for d in offset:
dy = y + d[0]
dx = x + d[1]
if 0 <= dy < n and 0 <= dx < m:
if grid[dy][dx] == 1: # 이동 가능한 칸
queue.append((dy, dx))
grid[dy][dx] = value + 1 # 거리 저장3. 결과 출력
print(grid[n-1][m-1])전체 코드
import sys
from collections import deque
readline = sys.stdin.readline
n, m = map(int, readline().split())
grid: list[list[int]] = []
# grid 초기화
for _ in range(n):
line = readline().rstrip()
row = []
for c in line:
row.append(int(c))
grid.append(row)
queue = deque([])
queue.append((0, 0))
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상, 하, 좌, 우
while queue:
v = queue.popleft()
y = v[0]
x = v[1]
value = grid[y][x]
for d in offset:
dy = y + d[0]
dx = x + d[1]
if 0 <= dy and dy < n and 0 <= dx and dx < m:
if 1 == grid[dy][dx]:
queue.append((dy, dx))
grid[dy][dx] = value + 1
if dy == n and dx == m:
break
print(grid[n-1][m-1])코드 설명
1. 입력 처리
n, m = map(int, readline().split())
grid: list[list[int]] = []
for _ in range(n):
line = readline().rstrip()
row = []
for c in line:
row.append(int(c))
grid.append(row)- 미로의 크기 N, M 입력
- 미로 정보를 문자열로 받아서 정수 배열로 변환
1: 이동 가능한 칸,0: 이동 불가능한 칸
2. BFS 초기화
queue = deque([])
queue.append((0, 0))- 시작 위치 (0, 0)을 큐에 추가
- 인덱스는 0-based이므로 (1, 1)은 (0, 0)에 해당
3. BFS 탐색
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상, 하, 좌, 우
while queue:
v = queue.popleft()
y = v[0]
x = v[1]
value = grid[y][x]
for d in offset:
dy = y + d[0]
dx = x + d[1]
if 0 <= dy < n and 0 <= dx < m:
if grid[dy][dx] == 1:
queue.append((dy, dx))
grid[dy][dx] = value + 1- 상하좌우 네 방향을 확인
- 범위 체크:
0 <= dy < n and 0 <= dx < m - 이동 가능한 칸(값이 1)을 발견하면 큐에 추가하고 거리 저장
value + 1로 저장하여 한 칸씩 증가
4. 결과 출력
print(grid[n-1][m-1])- 목표 위치 (N-1, M-1)의 값이 최소 칸 수
- 시작 위치가 1이므로 이미 정확한 값
시간 복잡도
-
시간 복잡도: O(N × M)
- 모든 칸을 최대 한 번씩 방문
- 각 칸에서 상하좌우 확인은 상수 시간
-
공간 복잡도: O(N × M)
- 그리드 저장: O(N × M)
- 큐: 최악의 경우 O(N × M)
풀이 포인트
1. 거리 저장 방식
그리드에 직접 거리를 저장하는 방식을 사용합니다:
- 시작 위치: 1
- 다음 칸: 2
- 그 다음 칸: 3
- …
이렇게 하면 별도의 거리 배열 없이도 최단 거리를 구할 수 있습니다.
2. 방문 표시
이 코드는 방문 표시를 명시적으로 하지 않고, 그리드 값을 변경하여 방문 표시를 합니다:
- 원래 값이 1인 칸을 방문하면 값이 2 이상으로 변경됨
- 따라서
grid[dy][dx] == 1체크만으로 방문 여부 확인 가능
3. 인덱스 주의
- 문제에서는 (1, 1)부터 시작하지만, 코드에서는 0-based 인덱스 사용
- (1, 1) → (0, 0)
- (N, M) → (N-1, M-1)
개선된 코드
명시적인 방문 배열을 사용하는 방법:
import sys
from collections import deque
readline = sys.stdin.readline
n, m = map(int, readline().split())
grid = [list(map(int, readline().rstrip())) for _ in range(n)]
queue = deque([(0, 0)])
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
y, x = queue.popleft()
if y == n - 1 and x == m - 1:
break
for dy, dx in offset:
ny = y + dy
nx = x + dx
if 0 <= ny < n and 0 <= nx < m:
if grid[ny][nx] == 1 and not visited[ny][nx]:
visited[ny][nx] = True
grid[ny][nx] = grid[y][x] + 1
queue.append((ny, nx))
print(grid[n-1][m-1])관련 문제
- BFS (너비 우선 탐색) - 2D 그리드 BFS 이론
- BOJ 14940: 쉬운 최단거리 - 2D 그리드에서 최단 거리 구하기
- BOJ 7576: 토마토 - 다중 시작점 BFS