📚 2178 - 미로 탐색

미로 탐색

이해

• 최소칸의 수를 구해야한다.
• 최단 거리를 구할 때는 bfs를 사용해야 한다.
• 점들을 지날 때마다 +1을 해줌으로써 '여기는 지났습니다.'라고 표시해주어야한다!
• 좌우위아래 좌표로 구해야한다.

소스

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())

x_coordinate = [-1, 0, 1, 0]
y_coordinate = [0, 1, 0, -1]

graph = []

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().strip())))


def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        temp = queue.popleft()

        for i in range(4):
            nx = temp[0] + x_coordinate[i]
            ny = temp[1] + y_coordinate[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] += graph[temp[0]][temp[1]]

                queue.append((nx, ny))


bfs(0, 0)

print(graph[n - 1][m - 1])

실행 결과