백준 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)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

내 코드

 

import sys
from collections import deque

def bfs(a,b):
    que=deque() #deque 생성.
    que.append([a,b])

    while que: #que 안에 확인할 놈들을 넣어둘건데, 다 비우면 빠져나오기
        x,y=que.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: #좌표 범위 밖이면 X
                continue
            if arr[nx][ny]==0: #이 좌표가 길이 아니면 X
                continue

            if arr[nx][ny]==1: #좌표 값이 1이라는 뜻->아직 방문X+길 임을 의미!!
                arr[nx][ny]=arr[x][y]+1 #이동하기전의 좌표에 있는 이동횟수+1을 저장.
                que.append([nx,ny]) #que에 집어넣어서 탐색 대상으로 처리.
                
    return arr[n-1][m-1] #결국 마지막 좌표에 있는 값이 최소이동 횟수가 된다.


#메인 코드.

#북동남서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

#n:세로길이, m:가로길이
n,m=map(int,sys.stdin.readline().split())

arr=[] #미로 지도 저장
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().rstrip())))

print(bfs(0,0)) #정답 출력.

 

풀이 및 접근)

- 탐색 관련 문제를 DFS로만 풀다보니 BFS에 대해 헷갈리는 부분이 많았었다. BFS, DFS 둘다 방법만 다를뿐 같은 방식의 탐색으로 알았다. 그러다보니 최단거리를 구하기 위해 min 값 등을 도입해서 따로 최소값을 저장해둘 생각을 하였다. 하지만 그렇게 하는 것이 아니라 BFS를 통해 최단거리를 구할 수 있었다.

- 이전의 DFS나 BFS 문제에서는 visited라는 리스트를 방문처리를 위해 도입했었다. 하지만 이 문제에서는 그러는 것이 비효율적이다. 방문 가능한 점들이 1(길)로 되어있고 불가능한 점들이 0(벽)으로 되어있다. 만약 특정 점을 방문시 이를 방문처리해야하는데, 이 문제에서는 그 좌표의 값을 +1 시켜주면 된다. 특정 점까지의 이동횟수를 저장함과 동시에 방문했음을 알 수 있다. 방문가능한 점들중에 아직 방문하지 않은 점들은 1로 남아있을 것이다. 이를 이용한 것이다.

- 위의 메커니즘을 이해하였으면 나머지는 일반적인 BFS 문제와 크게 다를 것이 없다. 마지막 좌표에 최종 최단거리가 저장되어 있다.