[BaekJoon] 백준 2178번 : 미로 탐색

2178번 : 미로 탐색

[BaekJoon] 1389번 : 케빈 베이컨의 6단계 법칙 과 [BaekJoon] 1012번 : 유기농 배추 를 섞어 놓은 문제이다.

유기농 배추와 마찬가지로 1인 곳을 찾아 BFS 를 수행하며 케빈 베이컨 처럼 그 좌표 까지의 거리를 저장 해 주면 된다.

(0, 0) 을 기준으로 갈 수 있는 오른쪽, 아래쪽이 2로 바뀌었다.

이어서 (1, 0) 을 기준으로 갈 수 있는 오른쪽, 아래쪽이 3으로 바뀌었다.

어차피 미로라서 모두 연결되어있기 때문에 BFS는 한 번만 수행하면 된다.

---

import sys
from collections import deque


def escape_maze(arr, x, y):
	start = [x, y, 1]
	queue = deque([start])

	while queue:
		dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		visit = queue.popleft()
		i, j, dist = visit[0], visit[1], visit[2]

		for cur in dirs:
			if 0 <= i + cur[0] < N and 0 <= j + cur[1] < M and arr[i + cur[0]][j + cur[1]] == 1:
				queue.append([i + cur[0], j + cur[1], dist + 1])
				arr[i + cur[0]][j + cur[1]] = dist + 1


N, M = map(int, input().rsplit())
_arr = [[int(x) for x in sys.stdin.readline().rsplit()[0]] for _ in range(N)]
escape_maze(_arr, 0, 0)

print(_arr[N - 1][M - 1])