[파이썬/백준 2178] 미로 탐색 BFS

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

처음에는 모든 경로 탐색하는 문제에 익숙해져있어서 DFS를 사용해서 구현했다가 시간초과로 실패했다.

그래서 알아보니 BFS와 DFS에는 다음과 같은 차이가 있었다.

 

BFS :

1. 최단 경로를 보장한다. 
2. 두 노드간의 최단(임의) 경로를 찾고 싶을 때 사용한다.
3. 큐를 사용한다.
4. 재귀를 통해 구현할 수 없다.

 

DFS :

1. 모든 경로를 탐색한다. → 시간복잡도가 매우 커진다.
2. BFS 보다 구현이 간단하다.
3. 스택을 사용한다.
4. 재귀를 통해 구현할 수 있다.

from collections import deque

def solution():
    # input 처리
    N, M = map(int, input().split())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, list(input()))))
    
    # bfs를 위한 자료구조
    # 동서남북
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    # graph와 똑같은 사이즈의 리스트(방문 여부, 방문한 곳의 수를 표시)
    visited = [[0 for _ in range(M)] for _ in range(N)]

    def bfs(i, j):
    	# 출발
        visited[0][0] = 1
        
        queue = deque([(0, 0)])
        while queue:
            x, y = queue.popleft()
            # 목적지에 도착하면 중단
            if x == N-1 and y == M-1:
                print(visited[x][y])
                break
			# 동서남북
            for i in range(4):
                next_x = x + dx[i]
                next_y = y + dy[i]
                # 리스트의 크기를 벗어나지 않는지 검사
                # & 방문하지 않은 곳이 맞는지, 방문할 수 있는 곳인지(길이 맞는지) 검사
                if 0 <= next_x <= N-1 and 0 <= next_y <= M-1\
                and visited[next_x][next_y] == 0 and graph[x][y] == 1:
                	# 방문한 곳으로 표시
                    visited[next_x][next_y] = visited[x][y] + 1
                    # 다음에 방문할 곳
                    queue.append((next_x, next_y))
		# 목적지까지 가기위해 방문한 곳의 개수를 리턴
        return visited[-1][-1] 

    return bfs(0, 0)

solution()

BFS는 어떤 노드를 방문했는지(visited)를 검사하지않으면 무한루프에 빠질 수 있어서 꼭 검사를 해야한다.