[BOJ/백준] 2178번 미로 탐색 (Python 파이썬)
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
| 1 초 | 192 MB | 133545 | 57116 | 36753 | 41.488% |
문제
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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
4 6
101111
101010
101011
111011
예제 출력 1
15예제 입력 2
4 6
110110
110110
111111
111101
예제 출력 2
9
예제 입력 3
2 25
1011101110111011101110111
1110111011101110111011101
예제 출력 3
38
예제 입력 4
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
예제 출력 4
13
풀이
여러 문제에서 등장하는 미로 탐색 유형의 기본 버전 문제같습니다.
미로 문제를 풀 때 어떻게 이동을 조작할 지에 대해서 다뤄보겠습니다.
우선 2차원 기준으로 문제가 구성되어있기 때문에 2차원에 맞춰서 작성하겠습니다.
x와 y에 대해서 변화량을 나타내는 dx와 dy를 선언합니다.
문제에서 정의하기를, 가능한 움직임은 총 4가지로 {위, 아래, 오른쪽, 왼쪽}입니다.
이를 dx와 dy로 나타내면 어떻게 될까요? 다음과 같습니다.
# 미로 문제 풀 때는 이동을 표현해준다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]이렇게 dx와 dy를 선언하면 특정 좌표에서 움직일 수 있는 4가지 경우의 수를 for문을 통해서 간편히 나타낼 수 있습니다.
여기서 무작정 4가지 움직임을 모두 고려해서는 안됩니다. 항상 움직임을 적용할 때는 미로의 조건을 확인해야 합니다.
해당 문제에서는 우선 미로의 범위를 확인해야 합니다. 즉, 특정 좌표에서 내가 움직일 때 미로를 벗어나지는 않는지 확인해야 하는 것이죠. 여기에 여러가지 제약조건이 추가된다면 조건문의 조건만 추가해주면 됩니다.
for i in range(4):
next_x, next_y = x+dx[i], y+dy[i]
if 0 <= next_x < N and 0 <= next_y < M: # 범위 확인
something happen이렇게 작성하면 미로에 벗어나지 않는 경우에 대해서 특정 동작을 수행할 수 있죠
자 이제 목적지까지의 최단 경로를 구하여 지나는 칸 수를 출력해야 합니다.
최단 경로를 구하기 위해서는 DFS와 BFS 중 어느 탐색을 사용해야 할까요?
DFS가 유리한 경우
- 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색하는 경우
- Graph의 크기가 클 경우
- Optimal한 답을 찾는 것이 아닌 경우
- 경로의 특징을 저장해야 하는 경우 ex) 경로의 가중치, 이동 과정에서의 제약
BFS가 유리한 경우
- 최단 거리 or 최단 횟수 구하는 경우
- Optimal한 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최단 거리이다!
- 탐색의 횟수를 구해야 하는 경우(7576번 토마토 문제)
답은 BFS입니다. BFS는 항상 최단 경로를 보장하기 때문이죠. 파이썬은 따로 queue를 구현한 자료구조가 없기 때문에 deque를 통해서 queue 자료구조의 동작을 구현해 줍시다.
만약에 특정 경로를 아직 방문하지 않았다면 큐에 담아서 탐색을 진행합니다.
추가로, 지나는 칸 수를 구하기 위해서 따로 값을 저장할 수 있지만 좀 더 효율적인 방법을 사용할 수 있습니다.
마치 DP문제를 풀듯이 graph의 value 자체를 이동 횟수로 저장하면서 탐색을 진행하는 것입니다.
# BFS
while queue:
x, y = queue.popleft()
for i in range(4):
next_x, next_y = x+dx[i], y+dy[i]
if 0 <= next_x < N and 0 <= next_y < M: # 범위 확인
if graph[next_x][next_y] == 1: # 경로 확인
queue.append((next_x, next_y))
graph[next_x][next_y] = graph[x][y] + 1 # value 자체를 이동 횟수로 사용
graph[next_x][next_y] == 1 이라는 것은, 내가 움직이려는 곳이 "이동 가능하며" 아직 한 번도 가보지 않은 곳임을 뜻합니다. 따라서 내가 움직인 자리( == graph[x][y])에서 한 번 움직였기 때문에 graph[next_x][next_y]에서의 이동 횟수는 거기에 1을 더하면 되는 것이죠.
최종 코드
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
# 2차원 리스트 생성
graph = [list(map(int, ' '.join(input().split()))) for _ in range(N)]
queue = deque([(0, 0)])
# 미로 문제 풀 때는 이동을 표현해준다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
cnt = 0
# BFS
while queue:
x, y = queue.popleft()
for i in range(4):
next_x, next_y = x+dx[i], y+dy[i]
if 0 <= next_x < N and 0 <= next_y < M: # 범위 확인
if graph[next_x][next_y] == 1: # 경로 확인
queue.append((next_x, next_y))
graph[next_x][next_y] = graph[x][y] + 1 # value 자체를 이동 횟수로 사용
print(graph[N-1][M-1])