[이취코] 미로 탐색

출처 : 이것이 취업을 위한 코딩 테스트다 with python

같은 문제 : https://www.acmicpc.net/problem/2178

 

 

---

문제는 링크에 있는 백준에 들어가서 보면 된다. 이 문제 같은 경우는 경로의 길이를 세는 것이기 때문에, BFS로 해야 효과적으로 해결할 수 있다. BFS는 너비우선탐색으로 시작 지점에서 가까운 노드부터 차례대로 모든 노드를 탐색하기 때문이다. DFS는 재귀를 이용해 깊이 우선 탐색을 한다면, BFS는 큐로 어느 정도 탐색하는 지를 볼 수 있다.

 

여기 풀이에서 특이한 점은 경로의 길이가 원래 노드 값(0,1)을 대체하게끔 푼다는 점이다. 경로의 길이가 노드 값을 대체하기 때문에 마지막 (N-1, M-1) 좌표에서 대체된 값을 출력하면 원하는 결과를 얻을 수 있다.

 

from collections import deque

N, M = map(int,input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input())))

# 상, 하, 좌, 우 이동 방향 결정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x,y): # (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 nx<0 or ny<0 or nx>=N or ny>=M: # 범위를 벗어나면 패스
                continue
            if graph[nx][ny] == 0: # 못 가는 곳이면 패스
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1 # 방문경로의 길이값으로 graph 대체
                queue.append((nx,ny)) # 이동한 (nx,ny) 좌표를 queue에 넣어서 모든 경로를 다 파악할 수 있도록

    return graph[N-1][M-1] # 최종 (N-1,M-1) 좌표에 대체된 값(방문경로 길이)을 리턴

print(bfs(0,0))