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

난이도 : 실버 1
유형 : BFS
https://www.acmicpc.net/problem/2178

---

문제 접근

최단거리를 구할땐 DFS 가 아닌 BFS 를 써야 한다.

(1,1) ,즉 맨 왼쪽위부터 시작했을 때(단 여기서는 인덱스 1,1이 첫번쨰다)
1이라고 되어있는 곳만 지나쳐 (N,M) 으로 가는 최소값을 출력해주는 문제이다.

graph[x][y] = graph[이전 x][이전 y] + 1
→ 이 방식으로 거리 정보를 누적해서 저장한다.
graph 자체를 거리 배열로 사용하기 때문에, 방문 여부 체크 배열이 따로 필요 없다.
0이면 벽이므로 continue 처리로 무시한다..

해답 및 풀이

import sys
from collections import deque
input = sys.stdin.readline

# 방향 벡터
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))

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

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

            # 범위 벗어나면 무시
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            # 벽이면 무시
            if graph[nx][ny] == 0:
                continue

            # 처음 방문한 곳이라면
            if graph[nx][ny] == 1:
                graph [nx][ny] = graph[x][y] + 1 
                queue.append((nx,ny))
                
# N,M 입력
N, M = map(int,input().split())
# 그래프 입력
graph = []
for _ in range(N):
    row = list(map(int,input().strip()))
    graph.append(row)

bfs(0,0)
print(graph[N-1][M-1])

# 마지막 표

행\열	0	1	2	3	4	5
0	1	0	9	10	11	12
1	2	0	8	0	12	0
2	3	0	7	0	13	14
3	4	5	6	0	14	15