[알고리즘] 백준 2178 파이썬 - 미로 탐색

 

2178번: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

 

문제풀이

import sys
from collections import deque
n,m=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input())))
def bfs(x,y):
	#01
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    q=deque([(x,y)])
    while q:
        x,y=q.popleft()
        for i in range(4):
        	#02
            nx=x+dx[i]
            ny=y+dy[i]
            #03
            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
                q.append((nx,ny))
    #04
    return graph[n-1][m-1]
print(bfs(0,0))

- #01 : dx,dy로 x,y 좌표가 이동할 수 있는 방향을 저장해놓는다.

           q의 초기값은 (x,y) 값으로 저장한다.

- #02 : nx와 ny에는 dx,dy의 값이 변함에 따라 for문을 통해 다른 좌표가 저장된다.

- #03 : 만약 nx,ny가 범위를 벗어나거나, nx,ny가 이동할 수 없는 좌표이면 continue한다.

           만약 이동이 가능하다면, 그 전 좌표 값에 1을 더한 값을 저장하고 q에 append한다.

- #04 : 최종적으로 graph[n-1][m-1] 값을 반환하고 출력한다.

           즉 처음 x,y 좌표를 1로 시작하여 다음 좌표로 방문 시 1을 더해 

           최종적으로 n,m에 도착했을 때는 지금까지 방문한 칸을 모두 누적한 값이 나온다.