[Python] BOJ 2178 - 미로 탐색(BFS)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

N * M칸의 map을 입력받고 BFS를 돌려준다.

1. (0,0)부터 시작하므로 q에 (0,0)을 넣고 BFS 시작

2. i가 0부터 3까지 돌면서 nx = x + dx[i], ny = y + dy[i]를 통해 현재 좌표의 상하좌우를 모두 '넓게' 탐색한다.

3. 만약 (nx,ny)를 방문한적이 없고 map[nx][ny]가 1이면 q에 넣고 dist[nx][ny]에 dist[x][y] + 1을 저장하고 (nx,ny)에

방문했다는 표시를 한다. (nx, ny가 맵 밖을 넘어가지않도록 범위 설정에 신경써주자!)

4. (N,M)위치로 이동해야 하므로 결국 dist[N-1][M-1]을 출력하면 도착위치로 이동하는 최소의 칸 수가 출력된다.

from collections import deque
N,M = map(int,input().split())
map = [list(input()) for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
q = deque()
visited = [[False] * M for _ in range(N)]
dist = [[0] * M for _ in range(N)]
visited[0][0] = True
dist[0][0] = 1
q.append((0,0))

while q:
	x,y = q.popleft()
	for i in range(4):
		nx, ny = x + dx[i], y + dy[i]
		if 0 <= nx < N and 0 <= ny < M:
			if not visited[nx][ny] and map[nx][ny] == '1':
				q.append((nx,ny))
				dist[nx][ny] = dist[x][y] + 1
				visited[nx][ny] = True
				
print(dist[N-1][M-1])

(solved.ac 티어: 실버 1)