미로 탈출 - bfs

오늘은 이것이 코딩테스트에서 미로 탈출 문제를 풀어보았다.

# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.

from collections import deque

# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    # N, M을 공백으로 구분하여 입력받기
    n, m = map(int, input().split())
    # 2차원 리스트의 맵 정보 입력받기
    graph = []
    for i in range(n):
        graph.append(list(map(int ,input())))

    # 이동할 네 방향 정의(상, 하, 좌, 우)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # BFS 소스코드 구현
    def bfs(x, y):
        # 큐(Queue) 구현을 위해 deque 라이브러리 사용
        queue = deque()
        queue.append((x,y))
        # 큐가 빌 때까지 반복
        while queue:
            x, y = queue.popleft()
            # 현재 위치에서 네 방향으로의 위치 확인
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # 미로 찾기 공간을 벗어난 경우 무시
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                # 벽인 경우 무시
                if graph[nx][ny] == 0:
                    continue
                # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx,ny))
            # 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n - 1][m - 1]
        # BFS를 수행한 결과 출력
    print(bfs(0, 0))

해당 문제를 풀다가 pycharm을 깔고 실행해보기위해서 깔고 reboot를 실행했는데 이전에

pythontutor에서 풀던 문제를 날려버리는 바람에 나의 답안은 버리게 되었다. 하지만 해당 방식은 dfs 방식이였기 때문에 위 방식이 답안이기 때문에 올바른 방식이다. 위 방식으로 한번 풀어보니 놀랍도록 멋진 코드인거 같다.