[백준] 2178 미로 탐색 파이썬

문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

 

 

풀이

from collections import deque
import sys

input = sys.stdin.readline

# N, M을 공백으로 구분하여 입력받기
N, M = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
maze = [list(map(int, input().rstrip())) for _ in range(N)]

# 이동할 네 방향 정의 (상, 하, 좌, 우)
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
            # 0인 경우 무시
            if maze[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))


bfs(0, 0)
print(maze[N - 1][M - 1])

 

BFS 방식으로 그래프를 순회하며 최단거리를 구하는 문제이다. 

 

queue에 시작부터 움직이는 동안의 위치를 담다 주고 하나씩 pop하며 해당 위치와 인접한 위치 중 움직일 수 있는 위치 (graph[x][y] == 1) 로만 움직여주고, 움직인 후에는 해당 그래프의 값에 1씩 더 해 이동거리를 기록해준다.