[정글 알고리즘] - [중] -백준 2178 미로 탐색 실버1

백준 실버 1 · BFS / 그래프 탐색

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

문제 요약

항목	설명
입력	N, M 그리고 0과 1로 이루어진 미로
이동 가능	상, 하, 좌, 우 인접 칸
의미	1은 이동 가능, 0은 이동 불가
목표	(1,1)에서 (N,M)까지 가는 최소 칸 수 구하기

왜 BFS를 써야 할까?

핵심

이 문제는 단순히 도착할 수 있는지만 보는 문제가 아니라, 최소 칸 수를 구하는 문제입니다. 이런 문제는 가중치가 없는 그래프의 최단거리 문제로 볼 수 있고, 가장 대표적인 풀이가 바로 BFS입니다.

BFS가 맞는 이유

BFS는 시작점에서 가까운 칸부터 차례대로 탐색합니다.

즉, 어떤 칸에 처음 도착했을 때의 거리가 그 칸까지의 최단거리입니다.

그래서 도착 지점에 처음 기록된 값이 곧 정답이 됩니다.

최종 코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(n)]

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

def bfs():
    q = deque()
    q.append((0, 0))

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 1:
                arr[nx][ny] = arr[x][y] + 1
                q.append((nx, ny))

bfs()
print(arr[n - 1][m - 1])

코드 한 줄씩 자세히 설명

줄	코드	설명
1	import sys	파이썬 기본 입력 함수인 input()보다 더 빠른 입력을 받기 위해 sys 모듈을 불러옵니다. 백준에서는 입력이 많을 때 자주 사용하는 방식입니다.
2	from collections import deque	BFS는 큐 자료구조를 사용합니다. 파이썬에서는 deque가 맨 앞에서 꺼내고 맨 뒤에 넣는 동작을 빠르게 처리할 수 있어 BFS에 적합합니다.
3		가독성을 위해 한 줄 띄운 부분입니다. 기능상 의미는 없지만 코드 구간을 나눠 보기 좋게 해줍니다.
4	input = sys.stdin.readline	앞으로 사용할 input을 빠른 입력 함수로 바꿔주는 코드입니다. 이후부터는 평소처럼 input()이라고 써도 실제로는 sys.stdin.readline()이 실행됩니다.
5		여기서도 입력 구간과 본격적인 문제 처리 구간을 구분하기 위해 한 줄 띄웠습니다.
6	n, m = map(int, input().split())	미로의 세로 크기 n과 가로 크기 m을 입력받습니다. 예를 들어 입력이 4 6이라면 n=4, m=6이 됩니다.
7	arr = [list(map(int, input().strip())) for _ in range(n)]	미로를 2차원 리스트로 저장하는 부분입니다. 각 줄은 예를 들어 101111처럼 공백 없이 들어오기 때문에 split()이 아니라 문자열 자체를 한 글자씩 숫자로 바꿔야 합니다. input().strip()으로 개행문자를 제거하고, map(int, ...)으로 각 문자를 정수로 바꾸고, list(...)로 한 줄을 리스트로 만듭니다. 이것을 n번 반복해서 전체 미로를 완성합니다.
8		방향 배열을 선언하기 전에 한 줄 띄워 구간을 분리한 것입니다.
9	dx = [-1, 1, 0, 0]	행 변화량입니다. 현재 위치에서 위로 가면 -1, 아래로 가면 +1, 좌우 이동은 행 변화가 없으므로 0입니다.
10	dy = [0, 0, -1, 1]	열 변화량입니다. 위아래 이동은 열이 그대로이므로 0, 왼쪽은 -1, 오른쪽은 +1입니다. 즉 dx[i], dy[i]를 같이 사용하면 상하좌우 네 방향을 한 번에 처리할 수 있습니다.
11		이제 BFS 함수를 정의하기 전이므로 한 줄 띄워줍니다.
12	def bfs():	BFS 탐색을 수행하는 함수를 정의합니다. 이 함수 안에서 시작점부터 도착점까지 거리 정보를 확장해 나가게 됩니다.
13	q = deque()	BFS에 사용할 큐를 만듭니다. 앞으로 방문할 좌표들을 이 큐에 저장하게 됩니다.
14	q.append((0, 0))	시작 좌표를 큐에 넣습니다. 파이썬 배열은 0번 인덱스부터 시작하므로 문제의 (1,1)은 코드에서는 (0,0)입니다.
15		시작점 입력이 끝났고, 이제 큐가 빌 때까지 탐색을 반복합니다.
16	while q:	큐에 아직 탐색할 좌표가 남아 있으면 계속 반복합니다. BFS는 큐가 완전히 빌 때까지 진행됩니다.
17	x, y = q.popleft()	큐의 맨 앞 좌표를 꺼냅니다. 먼저 들어간 좌표를 먼저 처리하기 때문에, 가까운 칸부터 순서대로 탐색하는 BFS가 됩니다.
18		현재 꺼낸 칸에서 갈 수 있는 네 방향을 검사하기 전 한 줄 띄운 부분입니다.
19	for i in range(4):	상, 하, 좌, 우 네 방향을 차례대로 확인합니다. 방향 배열 dx, dy와 연결해서 사용합니다.
20	nx = x + dx[i]	다음으로 이동할 칸의 행 좌표를 계산합니다. 현재 위치의 행 x에 방향에 따른 변화량을 더합니다.
21	ny = y + dy[i]	다음으로 이동할 칸의 열 좌표를 계산합니다. 이렇게 계산된 (nx, ny)가 실제로 갈 수 있는 칸인지 이제 확인해야 합니다.
22		다음 칸이 유효한지 검사하는 핵심 조건문 바로 전입니다.
23	if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 1:	이 줄이 정말 중요합니다. 조건은 크게 세 가지입니다. 1) 0 <= nx < n : 다음 행 좌표가 미로 범위를 벗어나지 않아야 합니다. 2) 0 <= ny < m : 다음 열 좌표도 범위 안이어야 합니다. 3) arr[nx][ny] == 1 : 그 칸이 이동 가능한 칸이면서 아직 방문되지 않은 칸이어야 합니다. 여기서 중요한 점은, 이 코드에서는 별도의 방문 배열을 만들지 않았다는 것입니다. 처음에는 갈 수 있는 칸이 전부 1이고, 방문하면 그 칸을 거리 값 2, 3, 4...로 바꾸기 때문에 다시는 1이 아니게 됩니다. 그래서 arr[nx][ny] == 1 조건만으로 방문 여부까지 함께 처리할 수 있습니다.
24	arr[nx][ny] = arr[x][y] + 1	다음 칸의 값을 현재 칸의 값보다 1 크게 바꿉니다. 예를 들어 현재 칸 값이 5라면, 그 칸까지 오는 데 5칸이 필요했다는 뜻이고, 거기서 한 칸 더 움직인 다음 칸은 6이 됩니다. 즉 이 줄은 단순히 방문 체크가 아니라 최단거리 기록 역할을 합니다.
25	q.append((nx, ny))	방금 방문 처리한 다음 칸을 큐에 넣습니다. 그러면 나중에 그 칸을 기준으로 또 상하좌우를 확장하게 됩니다. 이런 식으로 BFS가 한 층씩 퍼져 나갑니다.
26		조건문 블록과 반복문 블록이 끝나면서 BFS 함수 정의도 마무리됩니다.
27	bfs()	지금까지 정의만 해둔 BFS 함수를 실제로 실행합니다. 이 함수가 실행되면 시작점부터 미로 전체에 대해 최단거리 정보가 퍼져 나갑니다.
28	print(arr[n - 1][m - 1])	도착점의 값을 출력합니다. 배열 인덱스는 0부터 시작하므로 문제의 (N, M)은 코드에서는 (n-1, m-1)입니다. BFS가 끝난 뒤 이 칸에는 시작점에서 도착점까지 가는 최소 칸 수가 저장되어 있으므로, 그대로 출력하면 정답이 됩니다.

이 코드가 특히 좋은 이유

1. BFS의 정석 구조를 그대로 사용했다

큐를 만들고, 시작점을 넣고, 꺼내고, 네 방향을 확인하고, 조건을 만족하면 다시 넣는 흐름이 아주 전형적입니다.

2. 방문 배열 없이 거리 배열까지 한 번에 처리했다

원래 1이던 칸을 2, 3, 4처럼 거리 값으로 바꾸기 때문에 메모리도 아끼고 코드도 간결해집니다.

3. 도착점 값을 바로 정답으로 쓸 수 있다

별도의 거리 계산 결과를 저장할 필요 없이 마지막 칸의 값만 출력하면 됩니다.

자주 틀리는 부분

실수	왜 틀리는가
입력을 split으로 받는 경우	한 줄이 공백 없이 들어오기 때문에 원하는 2차원 배열이 만들어지지 않을 수 있습니다.
DFS로 최단거리를 구하려는 경우	도착은 가능해도 최소 거리 보장이 어렵습니다. 이 문제는 BFS가 핵심입니다.
방문 처리를 하지 않는 경우	같은 칸이 여러 번 큐에 들어가 비효율적이고, 거리 갱신도 꼬일 수 있습니다.
도착 좌표를 잘못 쓰는 경우	문제 좌표는 1부터 시작하지만 파이썬 인덱스는 0부터 시작하므로 arr[n-1][m-1]이어야 합니다.

마무리 정리

이 문제의 핵심 한 문장

가중치 없는 격자 최단거리 문제이므로 BFS를 사용하고, 방문한 칸에는 현재 칸 + 1을 저장해 최단거리와 방문 처리를 동시에 해결하면 됩니다.

문제 원문은 시작점에서 도착점까지 인접한 칸으로만 이동하면서 지나야 하는 최소 칸 수를 구하는 내용입니다. 따라서 BFS가 가장 자연스러운 정답 접근입니다. [문제 바로가기] [Source](https://www.acmicpc.net/problem/2178)