백준: 2178 미로 탐색

문제

2178번: 미로 탐색

 

문제 풀이

 시작 지점(0, 0)에서 도착 위치에 갈때까지 몇칸을 이동해야 하는지 찾는 문제이다. 시작 지점 부터 상, 하, 좌, 우로 탐색하면서 인접한 칸 중에 방문 가능한 칸이 있는지 확인 후에, 값을 중첩시키며 도착 위치에 이르렀을 때 몇칸을 이동했는지 출력하면 된다.

 위으 그림과 같이 예제 입력1, 2를 탐색하게 되면 도착 지점에 이르기까지 값을 중첩하면 답을 구할 수 있는 것을 알 수 있다. 처음에는 백트랙킹이 필요하지 않을까 생각했는데 그럴 필요 없이 값을 누적하며 탐색을 진행하면 된다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < m and graph[x][y] == 1


def bfs(start):
    q = deque([start])

    while q:
        cur_x, cur_y = q.popleft()

        for x, y in dirs:
            next_x, next_y = x + cur_x, y + cur_y
            if visitable(next_x, next_y):
                q.append([next_x, next_y])
                graph[next_x][next_y] += graph[cur_x][cur_y]

    return graph[n - 1][m - 1]


if __name__ == "__main__":
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().rstrip())) for _ in range(n)]
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    print(bfs([0, 0]))