[알고리즘][Python] 백준 2178 미로 탐색 문제 풀이

문제 출처 : www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

문제 해석 : 0과 1로 이루어진 배열에서 1은 이동가능한 것을 뜻한다. 여기서 1,1 에서 N,M으로 이동하는 최소 칸 수를 출력하는 문제이다.

 

문제 풀이 : 전형적인 탐색 문제로 여기서는 BFS를 이용해서 문제를 풀 수 있다. 거리를 기록하는 array와 방문 여부를 체크하는 array 두개를 이용해서 매 순간 가능한 모든 경로를 체크하면서 문제를 해결 할 수 있다. 

---

풀이 코드

from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, list(input()))) for _ in range(N)]

visited = [[False] * M for _ in range(N)]
dist = [[0] * M for _ in range(N)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

Q = deque()
Q.append((0,0))
dist[0][0] = 1
visited[0][0] = True

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx >= 0 and ny >= 0 and nx < N and ny < M:
            if visited[nx][ny] is False and arr[nx][ny] == 1:
                dist[nx][ny] = dist[x][y] + 1
                Q.append((nx, ny))
                visited[nx][ny] = True
print(dist[N-1][M-1])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.