[BOJ/Python] 미로 탐색 || BFS, 최단 경로
백준 미로탐색 파이썬 2178
https://www.acmicpc.net/problem/2178
❍ 문제
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
❍ 입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
❍ 출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
❏ 문제 풀이
BFS(너비 우선 탐색) 알고리즘을 사용하여 문제를 해결하고자 했다.
1. 입력 받기 : 미로의 크기와 정보를 입력받는다.
2. BFS 준비
- direction 리스트로 상하좌우 4방향 이동을 정의한다.
- visited 리스트로 각 칸에 대한 방문 여부를 체크한다.
- deque를 사용하여 BFS에서 활용할 큐를 준비한다.
3. BFS 실행
- 시작점(0,0)에서 시작한다.
- 큐에서 현재 위치와 이동 횟수를 꺼내고, 도착점인지 확인한다.
- 만약 도착점이 아닌 경우, 4방향으로 이동을 시도한다.
- 이동이 가능한 칸을 의미하는 1이고, 아직 방문하지 않은 칸이라면, 해당 칸을 방문 처리하고 큐에 추가한다.
4. 최종적으로 구할 수 있었던 최단 경로의 길이를 반환한다.
❍ Code
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
board = (
[[0] * (m + 2)]
+ [[0] + list(map(int, list(input().strip()))) + [0] for _ in range(n)]
+ [[0] * (m + 2)]
)
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = (
[[True] * (m + 2)]
+ [[True] + [False] * m + [True] for _ in range(n)]
+ [[True] * (m + 2)]
)
q = deque()
q.append((1, 1, 1))
visited[1][1] = True
result = int(1e9)
while q:
cnt, x, y = q.popleft()
if x == n and y == m:
result = min(result, cnt)
break
for dx, dy in direction:
nx = x + dx
ny = y + dy
if board[nx][ny] and not visited[nx][ny]:
visited[nx][ny] = True
q.append((cnt + 1, nx, ny))
print(result)
- board와 visited를 기존에 주어진 값에서 0으로 한번 더 감싸주게 되면, 추후에 4방향으로 이동할 때, 범위를 벗어나는지 확인해주지 않아도 된다.
❍ Code
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, list(input().strip()))) for _ in range(n)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * m for _ in range(n)]
q = deque()
q.append((1, 0, 0))
visited[0][0] = True
result = int(1e9)
while q:
cnt, x, y = q.popleft()
if x == n - 1 and y == m - 1:
result = min(result, cnt)
break
for dx, dy in direction:
nx = x + dx
ny = y + dy
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if board[nx][ny] and not visited[nx][ny]:
visited[nx][ny] = True
q.append((cnt + 1, nx, ny))
print(result)
- board와 visited를 0으로 감싸주지 않은 경우를 구현해보았다. 이 경우에는 4방향으로 이동 시에, 범위를 벗어나는지 확인해주어야 한다. 개인적으로 감싸주는 방안도 좋지만 이 방법이 더 손에 익은 것 같다.
❍ Code
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, list(input().strip()))) for _ in range(n)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * m for _ in range(n)]
q = deque()
q.append((1, 0, 0))
visited[0][0] = True
while q:
cnt, x, y = q.popleft()
for dx, dy in direction:
nx = x + dx
ny = y + dy
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if board[nx][ny] and not visited[nx][ny]:
visited[nx][ny] = True
q.append((cnt + 1, nx, ny))
board[nx][ny] = cnt + 1
print(board[-1][-1])
- count를 board에 그대로 반영해나아간다. BFS의 경우의 경우, 방문할 수 있는 경우의 수를 바로바로 방문처리하기 때문에 최단 경로를 구할 수 있는 특징을 활용해준 것이다.
- 따라서, 기존 코드와 다르게 board에 바로 count를 반영해주며 진행을 하고 최종적으로 도착점의 board의 값을 반환하면 된다.
❍ 시간 복잡도
- deque의 데이터 삽입 & 삭제 시간 복잡도 $O(1)$
- 최악의 경우, 모든 데이터를 삽입 & 삭제
BFS의 시간 복잡도는 O(V + E)이다.
- V = n x m, E = 4 x n x m
- 따라서, 시간 복잡도는 $O(n \times m)$