[BFS] 백준 #2178 미로 탐색하기 - Python

📚 문제

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

2178번: 미로 탐색

 

💡 접근법

미로에서 서로 인접한 칸으로만 이동하여 최단 거리를 구해야 하므로 BFS를 이용해야 한다.

BFS란?
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

해당 문제의 키 포인트는 2가지이다.

 

1. 미로 문제에서 이동을 조작하고 싶을 때 x, y에 대한 변화량을 나타내는 dx, dy를 선언한다.

 

문제에서 정의한 움직임은 총 4가지로, 상, 하, 좌, 우이다. 이를 dx와 dy로 나타내면 다음과 같다.
dx = [0, 0, 1, -1], dy = [1, -1, 0, 0]

또한 움직임을 적용할 때 미로의 범위를 확인해야 한다. 즉, 미로를 벗어나면 안 된다.
따라서 특정 좌표에서 미로 범위에 대한 조건문을 수행해야 한다.

2. 인접 리스트의 값 자체를 이동 횟수로 저장하면서 탐색을 진행한다. (DP와 유사한 방식)

 

(nx, ny) 좌표에 대하여 visited[nx][ny] == False and A[nx][ny] == 1을 만족한다면 이는 방문한 적이 없는 노드임을 뜻한다. 따라서 (x, y) 값에 +1을 한 값은 현재까지 이동한 거리(깊이)가 된다.

 

💻 코드

1) 전체 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

A = [[]]
visited = [[False] * (M+1) for _ in range(N+1)]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for _ in range(N):
    temp = list(map(int, sys.stdin.readline().strip()))
    temp.insert(0, 0)
    A.append(temp)


def BFS(v, w):
    queue = deque()
    queue.append((v, w))
    visited[v][w] = True
    while queue:
        node = queue.popleft()
        for k in range(4):
            nx = node[0] + dx[k]
            ny = node[1] + dy[k]
            if N >= nx > 0 and M >= ny > 0:
                if not visited[nx][ny] and A[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    A[nx][ny] = A[node[0]][node[1]] + 1


BFS(1, 1)
print(A[N][M])

 

2) 해설

(1) 패키지 Import

import sys
from collections import deque

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리, 큐를 사용하기 위해 collections.deque 모듈을 임포트한다.

 

(2) 입력받기

N, M = map(int, sys.stdin.readline().split())

A = [[]]
visited = [[False] * (M+1) for _ in range(N+1)]

for _ in range(N):
    temp = list(map(int, sys.stdin.readline().strip()))
    temp.insert(0, 0)
    A.append(temp)

도착 위치 좌표(N, M)를 입력받고, 인접 리스트(A)와 방문 리스트(visited)를 초기화한다.

for문을 순회하면서 인접 리스트, 즉 미로를 생성한다.

 

(3) BFS 구현

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def BFS(v, w):
    queue = deque()
    queue.append((v, w))
    visited[v][w] = True
    while queue:
        node = queue.popleft()
        for k in range(4):
            nx = node[0] + dx[k]
            ny = node[1] + dy[k]
            if N >= nx > 0 and M >= ny > 0:
                if not visited[nx][ny] and A[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    A[nx][ny] = A[node[0]][node[1]] + 1

deque()를 생성하고 현재 좌표를 튜플로 큐에 삽입한다.

현재 좌표에 대해 방문 리스트를 체크하고 큐가 빌 때까지 while 문을 수행하기 시작한다.

 

큐에서 노드를 꺼내고 현재 노드에서 인접한 칸을 상하좌우로 탐색한다.

이때 움직임을 적용한 좌표가 1) 미로의 범위를 벗어나지 않는지 2) 방문한 적이 없는 좌표인지 확인한다.

 

두 조건을 모두 만족할 경우 해당 좌표에 대한 방문 리스트를 체크하고 해당 좌표를 큐에 삽입한다.

또한 해당 좌표까지 이동한 거리를 직전 좌표까지 이동한 거리 + 1한 값으로 업데이트한다.

 

(4) 출력하기

BFS(1, 1)
print(A[N][M])

도착 지점 좌표까지의 거리를 출력한다.

 

✅ 정답 확인

 

---

 

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^