[Baekjoon] #2178 미로 탐색 (Python)

📝 문제

https://www.acmicpc.net/problem/2178

💬 풀이 방법

아이디어

그래프의 탐색을 활용하는 문제다. 깊이 우선 탐색(DFS)는 경로가 여러개 존재할 경우 모든 경로를 완전 탐색하고 그 중에서 최솟값을 찾는다. 따라서 시간이 굉장히 오래 걸리는 데에 비해 너비 우선 탐색(BFS)는 항상 최단 경로를 보장한다. 해당 문제는 경로의 특징에 영향을 받지 않고, 최단 경로만을 구하면 되기 때문에 BFS로 풀이하는 것이 적합하다.

알고리즘

1. 시작 지점의 좌표값을 collections 모듈의 deque 객체에 삽입하고, step 배열의 시작점을 1로 초기화한다.
2. deque 내부에 값이 존재하는 동안 popleft() 메서드를 사용하여 왼쪽에서부터 좌표 정보를 가져온다.
3. zip() 함수를 사용하여 방향 정보를 불러오고 다음으로 이동할 위치를 찾는다.
4. 다음 위치가 격자 내에 존재하고 방문하지 않은 곳이라면 해당 좌표의 정보를 deque에 삽입한다.
5. 현재 위치의 step 값을 이전 위치의 값 + 1로 설정한 뒤 다음 위치로 이동한다.
6. 탐색이 끝났다면 도착지점의 step 값을 반환한다.
   
   

💻 소스코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = []

for i in range(n):
	graph.append(list(input().rstrip()))

step = [([0] * m) for _ in range(n)]
visited = [([0] * m) for _ in range(n)]
q = deque()

def bfs():
	dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]

	while q:
		x, y = q.popleft()

		for dx, dy in zip(dxs, dys):
			nx, ny = x + dx, y + dy

			if (0 <= nx < m) and (0 <= ny < n) and graph[ny][nx] == "1" and not visited[ny][nx]:
				visited[ny][nx] = 1
				q.append((nx, ny))
				step[ny][nx] = step[y][x] + 1

q.append((0, 0))
step[0][0] = 1
bfs()
print(step[-1][-1])