[백준] 2178번 미로 탐색

단계별로 풀어보기 DFS와 BFS의 5단계 문제

2178번: 미로 탐색

BFS로 풀면 된다.

큐에 (row, col, depth)를 집어넣는다. (row, col)은 방문한 위치, depth는 (1, 1)부터 몇 칸 거쳐서 왔는지 정보이다.

from sys import stdin
import collections
n, m = list(map(int, stdin.readline().split()))
matrix = []
for i in range(n):
    matrix.append(stdin.readline())
q = collections.deque()
q.append((0, 0, 1))
visited = [[False] * m for i in range(n)]
while q:
    cur = q.popleft()
    if not visited[cur[0]][cur[1]]:
        visited[cur[0]][cur[1]] = True
        if cur[0] == n - 1 and cur[1] == m - 1:
            print(cur[2])
            break
    else:
        continue
    if cur[0] + 1 < n and matrix[cur[0] + 1][cur[1]] == "1" and not visited[cur[0] + 1][cur[1]]:
        q.append((cur[0] + 1, cur[1], cur[2] + 1))
    if cur[1] + 1 < m and matrix[cur[0]][cur[1] + 1] == "1" and not visited[cur[0]][cur[1] + 1]:
        q.append((cur[0], cur[1] + 1, cur[2] + 1))
    if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]] == "1" and not visited[cur[0] - 1][cur[1]]:
        q.append((cur[0] - 1, cur[1], cur[2] + 1))
    if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1] == "1" and not visited[cur[0]][cur[1] - 1]:
        q.append((cur[0], cur[1] - 1, cur[2] + 1))