[백준 2178] 미로 탐색 - 파이썬 (BFS, DFS 어떤 방법을 선택해야 할까)

백준 2178 - 미로 탐색

---

(언제쯤 적응될까 싶은 DFS, BFS...)

일단 탐색 문제는 DFS, BFS 중 어떤 방식을 사용해야 할지 문제에 따라 선택할 수 있어야 한다.

 

DFS는 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색해야 하는 경우에 적합하며,

BFS는 최단거리나 최단횟수와 같이 최적의 답을 찾아야 하는 경우에 적합하다.

 

2178번 문제의 경우, 최단 경로를 구해야 하므로 BFS를 활용하면 된다.

 

1) 시작점을 큐에 넣는다.

2) 큐의 가장 앞에 위치한 요소를 뽑아(`.popleft`) 방문처리한다.

3) 방문처리한 해당 요소의 인접한 요소 중 방문가능한 요소를 큐에 넣는다. 

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

maze = [[0 for _ in range(M+1)]]
visited = [[False for _ in range(M+1)] for _ in range(N+1)]

for i in range(N):
    str = sys.stdin.readline().split()[0]
    arr = [0]
    for i in str:
        arr.append(int(i))
    maze.append(arr)

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


def bfs(x, y):
    q = deque([(x, y)])
    
    while q:
        px, py = q.popleft()
        visited[px][py] = True
        
        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]

            if 0 <= nx <= N and 0 <= ny <= M:
                if not visited[nx][ny] and maze[nx][ny] == 1:
                    maze[nx][ny] = maze[px][py] + 1
                    q.append((nx, ny))
    return maze[N][M]
                    

print(bfs(1,1))

 

참고

https://great-park.tistory.com/46