[백준] 2178 미로탐색 python - BFS

문제링크: https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

예제 입력:
4 6
101111
101010
101011
111011

예제 출력:
15

풀이

과거에 풀었던 문제를 DFS/BFS 복기할겸 다시 풀어보았다.
최단거리라고 생각해서 DFS문제라고 생각했는데 과거에도 똑같은 방식으로 실수했던 기록이 있었다...(도대체 왜?) 문제를 다시 파악하고 BFS로 풀이하였다.

좌측 상단(1, 1)에서 우측 하단(4, 6)으로 이동하는 최소의 칸 수를 구하는 문제이다. 이것을 python list로 봤을때는 (0, 0)과 (n-1, m-1)이 된다.
아래 그림으로 보면 빨간 동그라미 지점에서 빨간 삼각형 지점으로 이동하는 최소칸의 수를 구하는 것이다.
*시작지점과 도착지점을 포함하는 조건이 있다.

출발지점과 도착지점

이동 경로는 아래와 같다. 사실 문제에서 이동경로는 중요하지 않지만 문제 파악을 위해 넣었다.

이동경로

 

정답 코드:

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

n, m = map(int, input().split())

miro = []
for i in range(n):
    miro.append(list(map(int, input().rstrip())))

#상하좌우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

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

	#queue가 빌 때까지 반복한다
    while queue:
        x, y = queue.popleft()     #이동하는 좌표

		#상하좌우 방향으로 탐색한다
        for i in range(4):
            nx = x + dx[i]	#이동한 위치는 nx가 된다
            ny = y + dy[i]

			#미로 범위를 벗어나는 이동은 불가능 하므로 continue
            if 0 > nx or nx >= n or 0 > ny or ny >= m:
                continue

			#미로 범위 안이더라도 0이라면 이동 불가능 하므로 continue
            if miro[nx][ny] == 0:
                continue
                
            #미로 범위 안이면서 1(이동가능)이라면
            if miro[nx][ny] == 1:
            
            	#이동한 좌표 = 기존의 좌표 + 1 을 해서, 1칸 이동한 값으로 갱신시켜준다
                miro[nx][ny] = miro[x][y] + 1
                # 갱신된 이동한 좌표를 queue에 append한다
                queue.append((nx, ny))

	#우측하단에 위치한 값을 return한다
    return miro[n-1][m-1]

print(bfs(0, 0))