[Python] BOJ/백준 2178번 미로 탐색

[문제]

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

2178번: 미로 탐색

 

[풀이]

🔥 DFS vs BFS

✨ DFS, BFS 모두 적합한 유형

• 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우

✨ DFS가 적합한 유형

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

✨ BFS가 적합한 유형

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

---

해당 문제는 모든 경우의 수를 구하지 않고 최단거리만 구하면 되기 때문에 BFS로 풀이했다.

 

1. 처음 시작 좌표(0, 0)를 데크에 넣은 후 데크가 비어있을 때까지 아래 2번을 반복해서 수행한다.
2. 현재 좌표에 대한 상, 하, 좌 우 좌표를 모두 탐색한다.
   1. 상하좌우 좌표가 미로의 범위(리스트범위)를 벗어나지 않고
   2. maze[nx][ny](다음좌표)의 값이 1이면
   3. 현재 좌표값 + 1 를 다음 좌표값에 갱신해준다.
   4. 데크에 다음 좌표값을 추가한다.
3. 탐색이 끝난 후 도착점 좌표 값을 리턴한다.

 

 

[코드]

import sys
from collections import deque


def bfs(node):
    # 상, 하, 좌, 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    map = deque()
    map.append(node)
    while map:
        x, y = map.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if maze[nx][ny] == 1:
                    maze[nx][ny] = maze[x][y] + 1
                    map.append((nx, ny))

    return maze[n-1][m-1]


n, m = map(int, sys.stdin.readline().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, sys.stdin.readline()[:-1])))
print(bfs((0, 0)))