[Python] 백준 #2178 - 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

풀이

import sys
from collections import deque

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x,y = queue.popleft()    
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx,ny))
    return graph[N-1][M-1]

N,M = map(int,input().split())
graph = [list(map(int,sys.stdin.readline()[:-1])) for _ in range(N)]

dx = [0,1,-1,0]
dy = [1,0,0,-1]

print(bfs(0,0))

 

미로의 최단거리를 찾는 문제이다. bfs로 풀면된다. 하지만 조금 변형되었기때문에 일반 bfs와는 조금 다르다.

 

 

 

일반 bfs와 다른점

 

• 모든 경우의 수를 다 봐야하기 때문에 방문한 노드를 체크하는 visited 리스트를 만들지 않는다
• 최단거리를 구해줘야하기 때문에 graph에 이동한 거리를 저장해줄 것이다. 

 

두번째 경우에서 잠깐 생각해 볼 것이 있다.

graph에는 1과 0이라는 이미 저장된 값이 존재한다. 그런데 여기에 이동한 거리를 넣어주게되면 1이 아닌 다른 값이 들어가게된다.(0은 갈 수 없으므로 항상 0)

갈 수 있는 길을 체크할때 1보다 큰 값이 들어가있다면 그것은 그 좌표에 현재 경로가 아닌, 더 빨리 도착할 수 있는 경로가 존재한다는 뜻이다. 그러므로 이제 현재 가고있는 경로로 해당 좌표에 도착하지 않아도 되기 때문에 이 좌표는 체크 할 필요가 없어진다. 그러므로 좌표를 체크할 때 1이면 큐에 넣어주는 식으로 해야한다.

 

 

 

 

본격적으로 코드를 보자.

 

먼저 입력된 값을 이중 리스트(graph)로 만들어준다. dx,dy는 상하좌우로 제어할 수 있는 리스트들이다.

가장 먼저 방문하는 (0,0) 좌표를 bfs에 넣어준다.

 

bfs 함수 코드를 보자.

그래프의 노드에 방문하면 좌우상하로 갈 수 있는 길을 찾는다.

갈 수 있는 길인지 확인하기 위해서는

 

1. 좌우상하로 이동한 좌표가 N,M의 범위내에 존재하는가
2. graph[nx][ny] 가 1인가 (왜 1인지는 위에서 설명하였다.)

이렇게 2가지를 체크해야한다.

두가지의 경우를 다 통과하여 갈 수 있다는 결론을 내리면 이동한 좌표에 원래의 좌표에 있던 값에 1을 더해준다.

 

큐에 체크해야하는 노드가 들어있지 않으면 반복문이 종료된다. 종료되면 graph[N-1][M-1]에 최단거리가 저장되있으므로 return해준다.