[DFS/BFS] 미로 탈출 (실전문제, 이것이 코딩테스트다 with 파이썬)

DFS (깊이 우선 탐색 알고리즘)

: 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

BFS (너비 우선 탐색 알고리즘)

: 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘

 

문제

 

해설

BFS 유형 : 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색

 

ex)

110

010

011

 

해당 입력을 예시로, 특정한 노드를 방문시에 이전 노드 거리 +1을 해서 값을 업데이트

1. 시작은 (1, 1)이며 해당 노드의 값은 항상 1
2. 상, 하, 좌, 우로 탐색을 진행하여 새롭게 방문한 (1, 2) 노드 값 2로 업데이트
3. 계속해서 1씩 증가하며 최단 경로로 이동

* 소스코드 상에서, 첫 번째 시작 위치는 재방문하여 3으로 변경될 여지가 있으나, 문제에서 단순히 오른쪽 아래로 이동하는 것을 요구.

 

풀이

from collections import deque

# 변수 : N, M 맵의 크기
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 변수 : graph 맵 정보 2차원 리스트
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# 이동할 네 방향 정의(상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]
    
# BFS를 수행한 결과 출력
print(bfs(0, 0))

 

해석

변수 : N M 맵의 세로 가로 크기, graph 맵 정보, dx dy 이동할 네 방향 정의, queue 넣었다 뺄 큐 자료구조, nx ny 이동 위치

 

1. 맵의 크기(N, M) 입력받기

2. 맵의 정보(graph) 입력받기

3. 이동할 네 방향(dx, dy) 정의

4. BFS 함수 정의 : queue가 빌 때까지

-----함수 내부-----

5. 해당 노드에서 네 방향(상, 하, 좌, 우) 방문 : 반복문

ㄴ 미로맵 벗어남 : continue

ㄴ 벽(0)이 있음 : continue

ㄴ 해당 노드 첫 방문 : 최단 거리 기록 & 큐에 입력

6. 최단 거리 반환 : graph[n - 1][m - 1]

-----------------------

7. BFS 함수 호출

 

* 최단거리 문제에는 BFS를 이용

* 전체에 대해 update가 수행되지만, 결론적으로 도착지점에 최단거리가 저장