[BOJ/백준] 2178. 미로 탐색 (Python)

🔎 문제

🔗 백준 2178번 미로 탐색

🤔 DFS VS BFS

DFS로 푸느라 삽질을 많이 한 문제이다..

DFS는 최단거리를 찾기 위해 완전 탐색을 하고 그중에서 최솟값을 구하게 되는데, 경로가 무수하게 많을 수 있어 매우 오랜 시간이 소요된다. 실제로 DFS로 풀이 후 제출하면 시간 초과가 난다.

반면 BFS는 최단거리를 보장한다. 이 미로탐색 문제는 모든 경우의 수를 구하지 않고 최단거리만 구하면 되게 때문에 BFS로 풀이한다.

📍 DFS, BFS 모두 적합한 유형

• 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 어떤 것을 택해도 된다.

📍 DFS가 적합한 유형

• 검색 대상 그래프가 큰 경우(정점과 간선의 개수가 많음)
• 경로의 특징을 저장해둬야 하는 문제
  • ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제
• BFS는 경로의 특징을 가지지 못함

📍 BFS가 적합한 유형

• 미로찾기 등 최단거리를 구해야 할 경우
• DFS는 처음으로 발견되는 해답이 최단거리 라는 것 보장 X
• 반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.

💡 풀이

생각의 흐름이 이렇게 된다.

1. BFS로 탐색하기로 결정(위에서 설명함)
2. BFS로 탐색하며 상, 하, 좌 우에 대한 루트를 모두 탐색한다.
3. 이때 상하좌우의 좌표가 미로의 범위(리스트범위)를 벗어난다면 그 길은 탈락
4. 또 maze[nx][ny](다음좌표)의 값이 1이 아니라면 탈락.
5. 위 두 조건에 위배되지 않는다면 현재 좌표값 + 1 를 다음 좌표값으로 갱신해준다. 이렇게 하면 탐색이 끝난 후 도착점 좌표의 값을 프린트해주면 그것이 답이다.
6. 5번과정과 함께 다음 좌표값을 큐에 추가해주어 BFS 탐색을 계속한다.

📌 collections.deque
BFS는 큐를 사용하기 때문에 효율이 좋지않은 리스트의 pop(0) 보단 deque의 popleft()를 사용한다.

📌 이동 경우의 수 설정하기

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# ...
for i in range(4):
    nx, ny = x + dx[i], y + dy[i]

x와 y에서 상, 하, 좌, 우로 이동한 좌표를 위에서 정의한 dx와 dy를 사용하여 for문을 돌아 간편하게 표현한다.

📃 소스코드

import sys
import collections
input = sys.stdin.readline
    
n, m = map(int, input().split())    
maze = [list(map(int, ' '.join(input()).split())) for _ in range(n)]

# 이동
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

Q = collections.deque([(0, 0)])
result = 0

while Q:
    x, y = Q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if maze[nx][ny] == 1:
                # 방문
                maze[nx][ny] = maze[x][y] + 1
                Q.append((nx, ny))

print(maze[n - 1][m - 1])

참고자료

• https://loosie.tistory.com/151
• https://velog.io/@lucky-korma
• http://blog.slarea.com/algorithm/techniques/dfs-bfs

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️