[백준] 2178번 - 미로 탐색 (Python3)

https://www.acmicpc.net/problem/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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

38

예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

13

 

 

 

내 풀이

일단 최단 거리 문제를 풀 때에는 BFS를 쓰는 것이 좋다. DFS를 사용해서 푸는 것은 최단 거리라는 보장이 없다.

라고 내가 1년 전에 필기했었다.

그래서 BFS로 풀어보았다.

 

import sys
import collections

N, M = map(int, sys.stdin.readline().split())
miro = []
for i in range(N):
    temp = list(map(int, sys.stdin.readline().rstrip()))
    miro.append(temp)

visit = [[0 for i in range(M)] for i in range(N)]
dq = collections.deque()
dq.append([0,0])
visit[0][0] = 1

while dq:
    now = dq.popleft()
    i, j = now[0], now[1]
    up = i - 1
    down = i + 1
    left = j - 1
    right = j + 1
    
    if i > 0 and miro[up][j] == 1 and visit[up][j] == 0:
        dq.append([up,j])
        visit[up][j] = visit[i][j] + 1
    if i < N-1 and miro[down][j] == 1 and visit[down][j] == 0:
        dq.append([down,j])
        visit[down][j] = visit[i][j] + 1
    if j > 0 and miro[i][left] == 1 and visit[i][left] == 0:
        dq.append([i,left])
        visit[i][left] = visit[i][j] + 1
    if j < M-1 and miro[i][right] == 1 and visit[i][right] == 0:
        dq.append([i,right])
        visit[i][right] = visit[i][j] + 1
print(visit[N-1][M-1])

방문한 지점을 표시하고 deque를 사용하는 것도 이전에 풀었던 노드 탐색 문제와 유사하다. 다른 점이 있다면 목적지까지 가기 위한 최소 칸 수를 구해야 하기 때문에 거쳐간 칸 수를 세줘야 한다.

이는 현재 칸 좌표의 visit에서 다음 칸 좌표의 visit으로 넘어갈 때 다음 칸 좌표에 현재 칸 좌표에서 1을 더한 값을 넣어주면 된다.

 

2번 예제의 경우를 그림을 그려서 설명해보자

왼쪽 : 미로          /         오른쪽 : visit

왼쪽 미로 그림을 보면 빨간색 동그라미로 표시한 경로가 최단 경로이다.

오른쪽 그림은 미로와 같은 형상의 visit 배열이고, 초기값은 모두 0이다.

시작점 (0,0) 위치의 visit에 1 값을 넣어준 다음, 인접하면서 이동이 가능한 칸으로 한 칸씩 1을 더한 값을 넣어주면서 넓혀가면 오른쪽 그림과 같이 된다.

원리가 잘 이해는 안되는데 그려보면 신기하게 최단거리의 수가 마지막 위치에 저장된다.

 

최단거리 문제 ====> BFS 일단 외우자