[Backjoon] 2178 미로 탐색 Python 문제 풀이

출처 : 미로 탐색

문제해석

대표적인 미로 탐색 유형의 쉬운 난이도 문제

미로 문제는 기본적으로 이동방향을 제어할 수 있는 배열이 자주 쓰인다.
(2차원 기준 2방,4방,8방 등)

y와 x좌표에 대한 변화량을 나타내는 dy,dx를 선언하여 각 방향별 인접배열 값을 탐색할 수 있다.

dy = [-1,1,0,0]
dx = [0,0,-1,1]

주의할 점은 이동조건이 있는 미로탐색 등의 문제에서 항상 경계체크와 이동조건을 잊지 말아야 한다.

다음으로 탐색할 인덱스가 전체 맵 배열의 최소와 최대 인덱스 범위를 벗어나지 않는지,
해당 문제에서는 배열값이 1로 되어 있는곳에서만 이동이 가능하므로 해당 조건 또한 동시에 만족해야 한다.

for d in range(4):
    ny, nx = y+dy[d], x+dx[d]
    if 0 <= ny < y좌표최대범위 and 0 <= nx < x좌표최대범위 and mapping[ny][nx]==1:
    경계체크 및 이동조건 만족시 수행

이 문제는 미로를 탐색하면서 목적지까지의 최단 경로를 구하는 문제이다.

최단 경로를 구하기 위해서 DFS와 BFS 중 어떤 탐색방식이 더 유리한가의 예시는 다음처럼 들 수 있다.

DFS
- 재귀적 특징과 백트래킹을 이용한 모든 경우를 하나씩 전부 탐색하는 경우
- 그래프(맵)의 크기가 클 경우
- 최적의 답을 찾는 것이 아닌 경우
- 경로의 특징을 저장해야 하는 경우 ex)가중치, 이동과정 제약 등

BFS
- 최단 거리 or 최단 횟수
- 최적의 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최적해
- 탐색의 횟수를 구해야 하는 경우

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제

• 단순히 모든 정점을 방문하는 것이 중요한 문제는 DFS,BFS 어느 것을 사용해도 무관.

2. 경로의 특징을 저장해둬야 하는 문제.

• 각 정점마다 숫자가 주어지고 a~b까지의 경로중 같은 숫자가 있으면 안된다는 식의 이동과정 제약 등의 문제 등, 각각의 경로마다 특징, 가중치 등을 저장해둬야 할 때는 DFS를 사용한다.(BFS는 경로의 특징을 가지지 못한다)

3. 최단거리

• 미로 찾기 등 최단거리 문제에서 BFS가 유리.
  DFS로 경로를 탐색할 경우 최초의 해답이 최적해(최단거리)가 아닐 수 있지만, BFS는 현재 노드부터 가장 가까운 곳부터 찾기 때문에 경로 탐색 시 가장 먼저 찾아지는 해답이 곧 최적해(최단거리)이기 때문.
• 따라서 최단 거리를 구하는 해당 문제는 BFS로 풀고자 한다.

1. 입력값으로 주어진 맵을 저장.
2. (1,1)좌표를 기준으로 bfs 시작.
3. 4방탐색으로 이동 가능한 인접노드 탐색.
4. (y,x)좌표가 n,m이 될때까지 인접노드 값을 증가하며 bfs 탐색.
5. (n,m)좌표에서 완성된 배열값 출력

해답코드

#미로 탐색
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int,input().split())
mapping = []

for _ in range(n):
    #readline 맨 뒤 '\n'까지 입력받으므로 제거해줘야함
    mapping.append(list(map(int,input().rstrip())))

dy = [-1,1,0,0]
dx = [0,0,-1,1]

def bfs(startY,startX):
    q = deque()
    q.append((startY,startX))
    while q:
        y,x = q.popleft()
        for d in range(4):
            ny = y+dy[d]
            nx = x+dx[d]
            if 0<=ny<n and 0<=nx<m and mapping[ny][nx]==1:
                q.append((ny,nx))
                mapping[ny][nx]=mapping[y][x]+1
    return mapping[n-1][m-1]

print(bfs(0,0))