문제
https://www.acmicpc.net/problem/2178
백준 2178번 - 미로 탐색 문제 풀이 전 문제 이해하기
이 문제는 '미로' 위를 출발점에서 도착점까지 최단거리로 이동하는 문제이다.
이동은 오른쪽, 왼쪽, 위, 아래 4가지 방향만 가능하며, 벽은 지나갈 수 없다.
즉, 최단거리 탐색 문제 = BFS 방식으로 풀어야 한다.
문제를 쉽게 이해하기 위한 준비
1. 아이디어 요약
- 큐 방식(BFS) 을 활용해 이동할 수 있는 경로를 탐색한다.
- 좌표 기준으로 큐에 넣는다.
- 예: [(x, y)] 형태 → 한 칸씩 이동
- 지도에서의 거리 기록은 graph 자체에 표시한다.
- 별도의 distance 리스트 없이, graph를 갱신하면서 거리 기록
- 시작점은 좌측 상단 (0,0)
BFS의 흐름 정리
- 출발 지점 : now = (0, 0)
- 큐에 시작점을 넣고 출발 : q = [(0, 0)]
- 이동 가능한 방향 : 왼(L), 오(R), 위(U), 아래(D) → 총 4방향
- 갈 수 없는 경우는 다음과 같다.
- 지도 바깥으로 나간 경우
- 벽인 경우 (0인 경우)
- 갈 수 있는 경우:
- 큐에 해당 위치 추가
- 그 위치의 값을 현재 위치 + 1로 갱신 → 거리 증가
앞에서 풀었던 "특정 거리 도시 찾기" 문제와의 비교
| 구분 | 특정 거리 도시 찾기 | 미로 탐색 |
| 지도 형태 | 노드 & 간선 (연결리스트) | 평면 격자 (2차원 리스트) |
| 인접 정의 | 연결된 도로 (정해진 노드) | 상하좌우 4방향 직접 계산 |
| 거리 기록 | 별도의 distance 리스트 | graph 자체에 거리 기록 |
| 사용 알고리즘 | BFS | BFS (반드시 BFS!) |
입력 처리 단계별 설명
이제 본격적으로 입력을 어떻게 처리하는지 한 줄씩 설명한다.
(1) 지도 크기 입력받기
n, m = map(int, input("가로 세로 크기 입력: ").split())- input() 함수로 사용자에게 지도의 크기를 입력받는다. 예: "4 6"
- "4 6" → .split()을 통해 공백 기준으로 "4", "6" 나눠진다.
- map(int, …)를 통해 문자열을 정수로 바꾼다 → [4, 6]
- n, m에 각각 할당되므로 n = 4, m = 6이 된다.
(2) 지도를 한 줄씩 받아서 2차원 리스트로 만들기
graph = []
for i in range(n):
t = input("지도에 대한 {0}번째 가로줄: ".format(i+1))
t = list(map(int, [i for i in t]))
graph.append(t)● 첫 줄
graph = []- graph는 전체 지도를 저장할 리스트이다.
- 지도를 한 줄씩 받아서 2차원으로 구성할 예정이므로 빈 리스트로 시작한다.
● for문
for i in range(n):- 총 n줄(세로 길이만큼)의 지도를 입력받아야 하므로 n번 반복한다.
- 각 줄마다 가로 방향의 정보가 입력된다.
● 사용자로부터 지도 한 줄 입력 받기
t = input("지도에 대한 {0}번째 가로줄: ".format(i+1))- 현재 몇 번째 줄인지 사용자에게 안내하며 입력을 받는다.
- 예: 101111 같은 문자열이 들어온다.
● 문자열을 숫자의 리스트로 변환
t = list(map(int, [i for i in t]))- 입력받은 문자열 "101111"을 리스트 컴프리헨션으로 한 글자씩 분리 → ['1','0','1','1','1','1']
- map(int, …)를 이용해 문자열을 정수로 바꾼다 → [1, 0, 1, 1, 1, 1]
- list()로 감싸서 다시 리스트 형태로 변환한다.
더보기
더보기
원래 코드
t = list(map(int, [i for i in t])) - t가 문자열이라면(예: "10111")
- [i for i in t] → 문자열의 각 문자를 리스트로 변환 → ['1','0','1','1','1']
- map(int, ...) → 리스트의 각 문자열 요소를 정수로 변환 → [1,0,1,1,1]
- list(...) → map 객체를 리스트로 만들어 최종 결과 [1,0,1,1,1]
for문으로 푼 버전
# 예: 사용자가 "10111" 입력
t_str = input().strip() # t_str = "10111"
t_list = [] # 변환된 숫자를 담을 빈 리스트 생성
for ch in t_str: # 문자열의 각 문자 ch를 하나씩 꺼냄
num = int(ch) # 문자 ch를 정수로 변환
t_list.append(num) # 변환한 숫자를 리스트에 추가
t = t_list # 이제 t는 [1,0,1,1,1] 동작 과정 예시
사용자가 "10111" 입력 → t_str = "10111"
- 첫 번째 반복
- ch = '1'
- num = int('1') → 1
- t_list.append(1) → t_list = [1]
- 두 번째 반복
- ch = '0'
- num = int('0') → 0
- t_list = [1, 0]
- 세 번째 반복
- ch = '1' → 1
- t_list = [1, 0, 1]
- 네 번째 반복
- ch = '1' → 1
- t_list = [1, 0, 1, 1]
- 다섯 번째 반복
- ch = '1' → 1
- t_list = [1, 0, 1, 1, 1]
결과
t = [1, 0, 1, 1, 1]이제 t는 문자열이 아니라 숫자로 구성된 리스트가 되어, BFS에서 1(길), 0(벽) 판별을 바로 할 수 있다.
● 변환된 리스트를 전체 지도에 추가
graph.append(t)- 변환한 리스트 t를 graph에 추가한다.
- 이 과정을 반복하면 graph는 아래처럼 구성된다 :
[[1, 0, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1]]정리
- 지도의 크기는 n x m 으로 입력받는다.
- 각 줄을 숫자의 리스트로 바꿔서 전체 graph를 구성한다.
- 이 그래프는 이후 탐색 과정에서도 활용되며, 거리 정보를 직접 갱신하는 데 사용된다.
- 다음 단계에서는 이 graph를 가지고 BFS를 통해 최단 경로를 구하게 된다.
최종 코드 설명
핵심 아이디어 요약
- BFS 탐색 사용
- 무조건 최단거리 → BFS만 가능 (DFS는 부적합)
- 큐(deque) 활용
- 앞으로 방문할 좌표들을 넣고 하나씩 꺼내며 탐색
- 거리 기록은 graph에 직접
- 따로 distance 배열 없이, 원래 지도에 바로 거리 기록
전체 코드
n,m = map(int, input("가로 세로 크기입력: ").split(" "))- 지도의 크기를 입력받는다.
- input() 함수로 문자열을 입력받고 → split(" ")으로 공백을 기준으로 나눈다
- "4 6" → ["4", "6"] → map(int, …)로 정수 변환 → n=4, m=6으로 저장
graph = []
for i in range(n):
t = input("지도에 대한 {0}번째 가로줄: ".format(i+1))
t = list(map(int, [i for i in t]))
graph.append(t)- graph는 지도를 저장할 2차원 리스트이다
- 총 n줄만큼 반복하여 한 줄씩 입력받는다
예시:
입력: 101111
→ '1','0','1','1','1','1' → [1,0,1,1,1,1]- 이렇게 변환한 리스트를 graph에 한 줄씩 추가하여 전체 지도를 만든다
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]- 상하좌우 4방향으로 움직이기 위한 좌표 변화값
- dx, dy는 각 방향에 따라 x축, y축이 어떻게 변하는지를 의미한다
- 왼쪽 (L): x+0, y-1
- 오른쪽 (R): x+0, y+1
- 위쪽 (U): x-1, y+0
- 아래쪽 (D): x+1, y+0
from collections import deque- deque는 큐(Queue)를 빠르게 처리할 수 있게 해주는 자료구조이다
- 일반 리스트보다 popleft()가 훨씬 빠르므로 BFS에 적합하다
BFS 함수 구현
def bfs_miro(start):- BFS 탐색을 위한 함수 정의이다
- start는 출발 좌표 (0,0)이 들어온다
q = deque()
x_pos, y_pos = start
q.append((x_pos, y_pos))
- 큐 q를 초기화한다
- 시작 위치인 (0,0)을 큐에 넣고, 탐색을 시작한다
while q:
- 큐가 빌 때까지 반복한다
- 즉, 앞으로 방문할 좌표가 없을 때까지 계속 진행한다
now_x, now_y = q.popleft()
- 현재 위치를 큐에서 꺼낸다
- 처음에는 (0,0)이 꺼내지며, 점점 다음 위치들이 추가된다
for i in range(4):
next_x = now_x + dx[i]
next_y = now_y + dy[i]- 현재 위치에서 상하좌우로 이동할 수 있는 다음 좌표들을 계산한다
if 0 <= next_x < n and 0 <= next_y < m:- 다음 위치가 지도 바깥으로 나가지 않는지 확인한다
- 파이썬 리스트 인덱스는 0부터 시작하므로 (0 ≤ x < n, 0 ≤ y < m) 조건 필요
if graph[next_x][next_y] == 1:- 다음 위치가 길인지 확인한다 (1인 경우)
- 벽(0)이거나 이미 방문한 경우(이미 숫자가 바뀐 경우)는 패스한다
graph[next_x][next_y] = graph[now_x][now_y] + 1- 다음 위치에 거리 값 갱신
- 현재 위치 값에 +1을 하여 다음 칸까지의 거리 기록
- 예: 출발점 1 → 다음칸 2 → 그다음 3...
q.append((next_x, next_y))- 방문 가능한 다음 위치를 큐에 추가하여,
- 이후에도 해당 위치에서 다시 네 방향 탐색을 하게 한다
BFS 실행
bfs_miro((0, 0))- (0,0) 출발점에서 BFS 탐색 시작
- 도착지점까지 가는 경로를 따라, graph에 거리값이 계속 갱신된다
결과 확인
graph- 탐색이 모두 끝난 후 graph를 출력하면,
- 각 칸에 도달하는 최소 거리가 적혀 있게 된다
- 도착점 (n-1, m-1)의 값이 바로 최단거리가 된다!
전체 코드 (정리)
python
코드 복사
n, m = map(int, input("가로 세로 크기입력: ").split(" "))
graph = []
for i in range(n):
t = input("지도에 대한 {0}번째 가로줄: ".format(i+1))
t = list(map(int, [i for i in t]))
graph.append(t)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
from collections import deque
def bfs_miro(start):
q = deque()
x_pos, y_pos = start
q.append((x_pos, y_pos))
while q:
now_x, now_y = q.popleft()
for i in range(4):
next_x = now_x + dx[i]
next_y = now_y + dy[i]
if 0 <= next_x < n and 0 <= next_y < m:
if graph[next_x][next_y] == 1:
graph[next_x][next_y] = graph[now_x][now_y] + 1
q.append((next_x, next_y))
bfs_miro((0, 0))
print("최단거리:", graph[n-1][m-1])
마무리 정리
- BFS는 최단 거리 탐색에 최적화된 알고리즘이다
- deque를 이용하여 큐 방식 탐색을 효율적으로 구현했다
- 이동 가능한 좌표만 조건 체크하여 큐에 추가하고, 거리 정보를 갱신했다
- 이 문제에서는 graph에 거리값을 직접 기록하는 방식을 사용해서, 별도의 distance 배열이 필요하지 않았다
'파이썬 > 코딩테스트' 카테고리의 다른 글
| [파이썬] 코딩테스트 17 기출_ 소수 구하기 문제 (3) | 2025.08.11 |
|---|---|
| [파이썬] 코딩테스트 16 구현_음료수 얼려먹기☆ (6) | 2025.08.08 |
| [파이썬] 코딩테스트 14 구현_최단거리 ☆ (0) | 2025.08.07 |
| [파이썬] 코딩테스트 13 구현_BFS (1) | 2025.08.07 |
| [파이썬] 코딩테스트 12 구현_DFS (2) | 2025.08.07 |