[백준] 2178번 미로 탐색(BFS알고리즘)(Python - 파이썬)

백준 2178번 문제입니다. (solved.ac)기준 실버 1 문제입니다.

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

예제 입력 1 :

4 6
101111
101010
101011
111011

예제 출력 1 :

15

문제에서 이동할 수 있는 칸은 1로 나타내고 이동이 불가능한 칸은 0(벽)으로 알려주었습니다. BFS알고리즘을 사용하여 이동이 가능한 칸인 1을 탐색하고 탐색할 때마다 직전 칸까지 이동하는데 걸린 칸수 +1 을 해주어 (N, M)까지의 이동간 지나는 칸수를 구하면 될 것 같습니다. 문제에서는 (1,1) ~ (N,M) 이지만 제 풀이는 받은 그래프가 (0,0)부터 시작하여 (0,0) ~(N-1,M-1)까지의 지나치는 칸수를 구하였습니다.

import sys
from collections import deque
# N은 행 M은 열
N, M = map(int,sys.stdin.readline().rstrip().split())
graph = []
#      상, 하, 좌, 우
dx = [-1, 1, 0, 0 ]
dy = [ 0, 0, -1, 1]

# 미로의 정보 입력받기
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

# BFS알고리즘 구현을 위해 deque() 사용
queue = deque()

# 미로가 (1,1)에서 시작한다고 문제에서 주어짐
# 입력 받은 graph 로는 (0,0)부터 시작
# 마찬가지로 (N, M)까지 이동할 때 지나야하는 최소 칸수를 구하는 것이지만
# 입력 받은 graph 로는 (N-1, M-1)까지 이동할 때 지나야하는 최소 칸수를 구하면 됨.
queue.append((0,0))

# queue가 빌 때 까지 반복
while queue :

    # 맨 처음 0,0 부터 탐색
    x, y = queue.popleft()

    # 상하좌우 방향으로 탐색
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]

        # 그래프 범위를 넘어가면 무시
        if nx < 0 or nx >= N or ny < 0 or ny >= M :
            continue
        # 탐색한 부분이 벽(0)이라면 무시
        if graph[nx][ny] == 0 :
            continue
        # 탐색한 부분이 1이라면 처음 탐색한 것이므로
        # 탐색 직전 graph값(탐색 직전 칸까지 이동할 때 지난 칸 수) + 1 (이동하는데 걸리는 칸수)
        if graph[nx][ny] == 1 :
            graph[nx][ny] = graph[x][y] + 1
            # queue에 nx,ny(탐색한 부분 삽입 후) 다시 탐색
            queue.append((nx,ny))

# (N, M)까지 이동할 때 지나야하는 최소 칸수를 구하는 것이지만
# 입력 받은 graph 로는 (N-1, M-1)까지 이동할 때 지나야하는 최소 칸수를 구하면 됨.
print(graph[N-1][M-1])