[BOJ, Python] 2178 - 미로 탐색 ( with BFS )

2178번: 미로 탐색

방해물을 피해 목표 지점까지 가는 가장 빠른 방법을 찾는 문제이다. DFS로 구현했을 때 시간 초과, 이어서 BFS로 구현했을 때에도 큐의 앞에서 요소를 하나씩 빼가며 탐색하는 방법이 아니라 큐를 통째로 탐색 후 새롭게 추가된 큐로 대체하는 방법을 사용했더니 역시 시간 초과가 나왔다. 결국 최초로 방문하는 지점에 인덱스를 저장하는 방식으로 구현, AC를 받았다.

# 빠른 입출력, deque 채택
import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    n, m = map(int, input().split())
    
    graph = list()
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    visit = [[False for _ in range(m)] for _ in range(n)]
    for _ in range(n):
        graph.append(list(map(int, list(input().rstrip()))))

    dq = deque()
    # x, y 좌표와 해당 좌표까지의 최단 거리 저장
    dq.append([0, 0, 1])
    visit[0][0] = True

    while dq:
        x, y, cnt = dq.popleft()
        
        # 목표 지점에 도달하면 return
        if x == n - 1 and y == m - 1:
            return cnt

		# 범위 내에서, 방문하지 않고 방해물이 아닐 때
        for (i, j) in zip(dx, dy):
            if (0 <= x + i < n) and (0 <= y + j < m):
                if not visit[x + i][y + j] and graph[x + i][y + j] == 1:
                    visit[x + i][y + j] = True
                    
                    # 다음 좌표와 거기까지의 최단 거리 저장
                    dq.append([x + i, y + j, cnt + 1])
print(bfs())