[Python] 백준 2178. 미로 탐색

bfs로 값이 1인 좌표를 탐색하는 문제.

한 번 1인 지점을 방문하면, 그 지점의 값을 0으로 바꾸는 식으로 중복탐색을 막을 수 있다.

 

 

	from collections import deque
	N, M = map(int, input().split())
	dirs = [(1,0), (-1,0), (0,1), (0,-1)]
	dist = [[0 for _ in range(M)] for _ in range(N)]
	maps = [list(map(int, list(input()))) for _ in range(N)]
	queue = deque()
	queue.append((0,0))
	dist[0][0] = 1
	while queue:
	cur_y, cur_x = queue.popleft()
	maps[cur_y][cur_x] = 0
	for i in range(4):
	nxt_y, nxt_x = cur_y + dirs[i][0], cur_x + dirs[i][1]
	if 0 <= nxt_y < len(maps) and 0 <= nxt_x < len(maps[0]) and maps[nxt_y][nxt_x] == 1:
	queue.append((nxt_y, nxt_x))
	dist[nxt_y][nxt_x] = dist[cur_y][cur_x] + 1
	maps[nxt_y][nxt_x] = 0
	print(dist[N-1][M-1])

view raw [백준] 미로 탐색.py hosted with ❤ by GitHub