2178_미로 탐색

입력

첫째 줄에 세로 길이 N과 가로 길이 M이 주어지고
둘째 줄에 NxM 크기의 "0"과 "1"로 된 미로가 주어진다.

출력

(0,0)에서 (N-1, M-1)까지의 최단 거리를 출력

조건

• 좌표 값이 "1"인 곳만 이동 가능
• 시간 제한 1초
• 0 <= N, M <= 100

풀이

처음에는 모든 경우의 수를 확인하며 최단 거리를 구하는 깊이 우선 탐색(dfs)를 사용하여 풀었다. 하지만 시간 초과가 발생하였다. 이후 생각을 해보니까 너비 우선 탐색(bfs)로 풀이가 가능한 문제였다는 것을 깨달았다.

1. 큐의 인자는 [y, x, cnt]로 이루어져 있으며 cnt는 (0,0)부터 해당 좌표까지의 이동 거리를 의미한다.
   초기 큐에 [0, 0, 1]를 추가하고 visited[0][0] = True로 설정한다.

q = deque([[0,0,1]])
visited[0][0] = True
print(bfs(q))

2. 상하좌우 4가지 경우를 확인하며 미로에서 다음에 참고할 좌표값이 "1"인 경우와 방문하지 않은 경우 다음에 참고할 좌표값의 visited를 True로 설정하고 큐에 [next_y, next_x, cnt+1]를 추가한다.

        for idx in range(4):
            next_x, next_y = x+dx[idx], y+dy[idx]
            if  next_y >= 0 and next_y < N and next_x >= 0 and next_x < M:
                if visited[next_y][next_x]==False and maze[next_y][next_x]=="1":
                    visited[next_y][next_x] = True
                    q.append([next_y, next_x, cnt+1])
            else: continue

3. 현재 좌표가 y==N-1 and x==M-1 일 경우 현재 이동 거리를 return한다.

        if y == N-1 and x == M-1: return cnt

---

처음에는 좌표를 방문했을 때 visited를 True로 설정하였지만 이럴 경우 겹치는 경우가 발생할 수 있다. 따라서 큐에 추가할 때 추가하는 좌표의 visited를 True로 설정해야지 너비 우선 탐색에서 중복이 발생하지 않는다.

전체 코드

미로 탐색