[알고리즘]백준 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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

 

풀이

초기에 start에 해당하는 원소는 2로 바꾸어줍니다. 

이유는 search_update라는 함수로 1인 부분을 탐색해나갈건데  시작지점[0,0]지점도 여기에 걸리기 때문입니다.

결론은 [0,0]를 탐색에 걸리지 않게 하기 위함입니다

 

serch_update함수는 현재 위치 start에서 상하좌우의 위치를 탐색합니다. 이때 그 부분의 값이 1이면 

이를 방문 가능한 위치로 판단하고 배열 arr에 추가해줍니다. 그리고 값을 현재 위치에서 +1을 해줍니다

 

이를 반복문을 통해 반복할건데 방문 가능한 위치 arr에서 원소를 하나씩 빼주면서 이를 통해 search_update를 해줍니다 

원소를 빼줄 때 deque자료형을 사용하여 popleft를 진행하였는데, (혹은 리스트 사용하여 pop(0)도 가능할 거 같습니다) 

그냥 pop을 사용해서 원소를 빼주면 갈림길이 있는 경우 한 방향으로 전체 탐색을 진행한 다음에, 다시 돌아가서

탐색을 진행하는데 각 갈림길을 선택했을 때의 최솟값이 다른 경우 정답과 다른 값이 나오게 됩니다 

pop을 사용하는 경우 탐색

  

import sys
from collections import deque
N,M = map(int,sys.stdin.readline().strip().split())
map_ =[]
for i in range(N):
    line = sys.stdin.readline().strip()
    line_arr =[]
    for chr in line:
         line_arr.append(int(chr))
    map_.append(line_arr) 
arr= deque([[0,0]])
map_[0][0]=2
def search_update(map_, start):
    i, j  =start[0], start[1]

    if map_[min(i+1,N-1)][j]== 1:
        arr.append([min(i+1,N-1),j])
        map_[min(i+1,N-1)][j] =map_[i][j]+1
        
    if map_[max(i-1,0)][j] ==1:
        arr.append([max(i-1,0), j])
        map_[max(i-1,0)][j]= map_[i][j]+1
        
    if map_[i][min(j+1,M-1)]==1:
        arr.append([i, min(j+1,M-1)])
        map_[i][min(j+1,M-1)]= map_[i][j]+1
        
    if map_[i][max(j-1,0)]==1:
        arr.append([i,max(j-1,0)])
        map_[i][max(j-1,0)]= map_[i][j]+1
    return map_, arr
while arr: 
    start =arr.popleft()
    map_, arr = search_update(map_, start)

print(map_[N-1][M-1]-1)