18강 / 20강

졸업 작품 — 미로를 탈출하는 프로그램

지금까지 배운 것을 전부 한자리에

드디어 종합입니다. 미로에서 출구까지 가장 짧은 길을 찾는 프로그램을 만듭니다. 이 하나의 문제에 지금까지 배운 자료구조가 거의 다 들어갑니다.

쓰이는 것	어디에	배운 곳
2차원 리스트	미로 지도 그 자체	2강
튜플	좌표 `(행, 열)` — 딕셔너리 열쇠로 써야 하니까	4강
집합	이미 가 본 칸 표시	4강
딕셔너리	각 칸의 직전 칸 기록 → 경로 복원	5강
큐 (deque)	BFS — 다음에 갈 칸들의 대기열	7강
스택	DFS 비교용, 경로 되짚기	6강
그래프 탐색	알고리즘 본체	15강

고등학생지금까지 배운 것을 전부 한자리에

졸업 작품입니다. 새로 배울 게 없어요.

배운 그릇들을 조립하면 미로가 풀린다

필요한 것들

쓰이는 것	왜	강
큐 (deque)	BFS 대기열	7·15
집합	본 곳 표시	4·15
튜플	좌표 (행, 열)	4
딕셔너리	어디서 왔는지	5
2차원 리스트	미로 자체	2

다섯 자료구조가 각자 자기 역할을 한다

왜 미로가 좋은 예제인가

이유	설명
그래프다	칸이 점, 이웃이 선 (14강)
최단 경로	BFS 가 딱 맞다 (15강)
눈에 보인다	맞는지 그림으로 확인된다

추상적인 그래프가 그림이 되니 이해가 쉽다

미로를 그래프로 보면

미로	그래프
빈 칸	정점
인접한 빈 칸	간선
벽	간선이 없다

"이웃 목록" 을 미리 만들지 않고 그때그때 계산한다

상하좌우 네 방향을 확인해서 벽이 아니고 범위 안이면 이웃이에요.

🎮 미로를 직접 그리고 풀어 보세요

칸을 클릭해 벽을 세우고, 출발·도착을 옮긴 뒤 BFS와 DFS를 각각 눌러 보세요. 방문한 칸 수와 찾은 경로의 길이가 어떻게 다른지가 핵심입니다.

고등학생좌표를 다루는 요령

격자 문제에는 정해진 요령이 있습니다.

방향을 리스트로 두면 코드가 짧아진다

방향 = [(-1,0), (1,0), (0,-1), (0,1)]   # 상하좌우

for dr, dc in 방향:
    nr, nc = r + dr, c + dc

이렇게 안 하면

if r > 0 and 미로[r-1][c] != '#': ...
if r < 행수-1 and 미로[r+1][c] != '#': ...
if c > 0 and 미로[r][c-1] != '#': ...
if c < 열수-1 and 미로[r][c+1] != '#': ...

거의 같은 네 줄 — 복사·붙여넣기는 실수의 온상

왜 복사가 위험한가

세 줄을 고치고 한 줄을 빠뜨리면 한 방향만 틀립니다. 그리고 찾기 어렵죠.

반복되는 코드는 자료로 바꾼다 — 프로그래밍의 기본 태도

대각선까지 하려면

방향 = [(-1,-1),(-1,0),(-1,1),
        ( 0,-1),        ( 0,1),
        ( 1,-1),( 1,0),( 1,1)]

코드는 한 줄도 안 바뀐다 — 목록만 늘렸다

범위 확인

if 0 <= nr < 행수 and 0 <= nc < 열수:

파이썬의 연쇄 비교가 편합니다. 수학 표기 그대로 읽히죠.

3강의 인덱스 경계 — 0부터 n-1 까지

비유 — 체스 말의 움직임

체스 프로그램도 이렇게 만듭니다.

말	방향 목록
룩	상하좌우 (계속)
비숍	대각선 (계속)
나이트	여덟 가지 특수 이동

규칙을 자료로 표현하면 코드는 하나로 끝난다

① 미로를 자료로 표현하기

격자는 리스트 안의 리스트입니다. 0은 길, 1은 벽. 좌표는 (행, 열) 튜플로 다룹니다 — 집합과 딕셔너리에 넣어야 하니까요.

미로를 그려 봅니다. 0을 1로 바꿔 벽을 세워 보세요.

Python 브라우저에서 실행

미로 = [
    [0, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 0],
]
출발, 도착 = (0, 0), (5, 6)

def 그리기(미로, 길=(), 본곳=()):
    for ㄹ, 줄 in enumerate(미로):
        칸들 = []
        for ㅋ, ㅂ in enumerate(줄):
            자리 = (ㄹ, ㅋ)
            if 자리 == 출발:   칸들.append("🚩")
            elif 자리 == 도착: 칸들.append("🎯")
            elif ㅂ == 1:      칸들.append("⬛")
            elif 자리 in 길:   칸들.append("🟩")
            elif 자리 in 본곳: 칸들.append("🟨")
            else:              칸들.append("⬜")
        print("".join(칸들))

그리기(미로)
print()
print(f"크기: {len(미로)}행 × {len(미로[0])}열, 벽 {sum(map(sum, 미로))}개")

② BFS로 최단 경로 찾기

15강에서 배운 그대로입니다. 큐에서 꺼내고, 상하좌우 이웃을 담고, 본 곳은 표시하고. 여기에 부모 딕셔너리를 하나 더해서, 도착한 뒤 거꾸로 되짚어 경로를 복원합니다.

고등학생경로를 복원하는 법

BFS 로 도착했다는 건 알았습니다. 그런데 어떤 길로 갔는지는요?

각 칸마다 "어디서 왔는지" 를 기록해 둔다

부모 = {시작: None}
...
if 이웃 not in 부모:
    부모[이웃] = 현재      # ← 어디서 왔는지
    대기.append(이웃)

그리고 거꾸로 따라갑니다

경로 = []
칸 = 도착
while 칸 is not None:
    경로.append(칸)
    칸 = 부모[칸]
경로.reverse()

도착에서 거꾸로 따라가면 시작에 닿는다

왜 거꾸로 저장하나

방향	가능한가
"여기서 어디로 갈까"	갈 곳이 여러 개 — 못 정한다
"여기로 어디서 왔나"	하나뿐 ✔

BFS 에서는 처음 도달한 경로가 유일하다 — 그래서 부모가 하나

비유 — 헨젤과 그레텔

숲에 들어가며 빵 조각을 떨어뜨립니다. 돌아올 때는 그걸 거꾸로 따라가죠.

갈 때	올 때
표시를 남긴다	표시를 따라간다

지나온 흔적이 돌아가는 길이 된다

6강과 연결됩니다

경로를 뒤집는 대신 스택에 쌓아도 됩니다. 꺼내면 저절로 순서가 맞죠.

"거꾸로 만들고 뒤집기" 와 "스택" 은 같은 것이다

BFS 본체. 큐 · 집합 · 딕셔너리가 한자리에 모입니다.

Python 브라우저에서 실행

from collections import deque

미로 = [
    [0, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 0],
]
출발, 도착 = (0, 0), (5, 6)
행수, 열수 = len(미로), len(미로[0])

def 이웃들(자리):
    ㄹ, ㅋ = 자리
    for ㄷㄹ, ㄷㅋ in [(-1,0), (1,0), (0,-1), (0,1)]:      # 상 하 좌 우
        ㄴㄹ, ㄴㅋ = ㄹ + ㄷㄹ, ㅋ + ㄷㅋ
        if 0 <= ㄴㄹ < 행수 and 0 <= ㄴㅋ < 열수 and 미로[ㄴㄹ][ㄴㅋ] == 0:
            yield (ㄴㄹ, ㄴㅋ)

def bfs(출발, 도착):
    본곳 = {출발}                    # 집합 (4강)
    부모 = {출발: None}              # 딕셔너리 (5강)
    ㄷ = deque([출발])               # 큐 (7강)
    방문순서 = []
    while ㄷ:
        지금 = ㄷ.popleft()
        방문순서.append(지금)
        if 지금 == 도착:
            break
        for 이웃 in 이웃들(지금):
            if 이웃 not in 본곳:
                본곳.add(이웃)
                부모[이웃] = 지금
                ㄷ.append(이웃)

    if 도착 not in 부모:
        return None, 방문순서
    길, 현재 = [], 도착              # 경로 복원 — 스택처럼 쌓았다 뒤집기 (6강)
    while 현재 is not None:
        길.append(현재)
        현재 = 부모[현재]
    return 길[::-1], 방문순서

길, 순서 = bfs(출발, 도착)
print(f"최단 경로: {len(길)}칸")
print(f"방문한 칸: {len(순서)}칸")
print(길)

🟩 찾은 경로, 🟨 살펴봤지만 안 쓴 칸. 둘을 비교해 보세요.

Python 브라우저에서 실행

from collections import deque

미로 = [
    [0, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 0],
]
출발, 도착 = (0, 0), (5, 6)
행수, 열수 = len(미로), len(미로[0])

def 이웃들(자리):
    ㄹ, ㅋ = 자리
    for ㄷㄹ, ㄷㅋ in [(-1,0), (1,0), (0,-1), (0,1)]:
        ㄴㄹ, ㄴㅋ = ㄹ + ㄷㄹ, ㅋ + ㄷㅋ
        if 0 <= ㄴㄹ < 행수 and 0 <= ㄴㅋ < 열수 and 미로[ㄴㄹ][ㄴㅋ] == 0:
            yield (ㄴㄹ, ㄴㅋ)

def 탐색(너비우선):
    본곳, 부모 = {출발}, {출발: None}
    담을곳 = deque([출발])
    while 담을곳:
        지금 = 담을곳.popleft() if 너비우선 else 담을곳.pop()   # ← 이 한 줄만!
        if 지금 == 도착:
            break
        for 이웃 in 이웃들(지금):
            if 이웃 not in 본곳:
                본곳.add(이웃); 부모[이웃] = 지금; 담을곳.append(이웃)
    길, 현재 = [], 도착
    while 현재 is not None:
        길.append(현재); 현재 = 부모[현재]
    return 길[::-1], 본곳

def 그리기(길, 본곳):
    for ㄹ in range(행수):
        줄 = ""
        for ㅋ in range(열수):
            자리 = (ㄹ, ㅋ)
            if 자리 == 출발:   줄 += "🚩"
            elif 자리 == 도착: 줄 += "🎯"
            elif 미로[ㄹ][ㅋ]: 줄 += "⬛"
            elif 자리 in 길:   줄 += "🟩"
            elif 자리 in 본곳: 줄 += "🟨"
            else:              줄 += "⬜"
        print(줄)

for 이름, 너비 in [("BFS (큐)", True), ("DFS (스택)", False)]:
    길, 본곳 = 탐색(너비)
    print(f"── {이름} ── 경로 {len(길)}칸 / 살펴본 칸 {len(본곳)}칸")
    그리기(set(길), 본곳)
    print()

고등학생결과를 읽는 법

note 가 결과 읽기를 설명합니다. 맞는지 확인하는 것도 중요한 능력이에요.

눈으로 볼 수 있으면 버그가 보인다

확인할 것들

확인	틀렸다면
경로가 이어져 있나	이웃 계산이 틀렸다
벽을 안 지나나	벽 확인이 빠졌다
길이가 최소인가	BFS 가 아니라 DFS 를 썼다
같은 칸을 두 번 안 지나나	표시가 빠졌다

각 증상이 어느 부분의 버그인지 대응된다

길이 없을 때

도착에 영영 못 닿으면 어떻게 되나요?

단계	결과
갈 수 있는 곳을 전부 본다	—
대기열이 빈다	while 이 끝난다
도착이 부모에 없다	"길이 없다" ✔

저절로 끝난다 — 따로 처리할 게 없다

좋은 알고리즘의 특징이에요. 예외 상황이 자연스럽게 처리됩니다.

BFS 를 DFS 로 바꿔 보세요

popleft() 를 pop() 으로 바꾸면 —

	BFS	DFS
길을 찾나	찾는다	찾는다
길이	최소	구불구불
탐색한 칸	넓게	한 방향으로

직접 바꿔 보면 15강이 몸으로 이해된다

같은 코드에서 한 글자가 바뀌었을 뿐인데 결과가 눈에 띄게 다릅니다.

③ 더 해 볼 것

대각선 이동을 허용해 보세요 — 이웃들의 방향 목록에 4개를 더하면 됩니다.
칸마다 이동 비용이 다르다면? (모래는 3초, 길은 1초) 큐 대신 힙(12강)을 쓰면 다익스트라 알고리즘이 됩니다.
미로를 자동 생성해 보세요 — DFS로 벽을 뚫으며 다니면 미로가 만들어집니다.

미로 생성기. 6강의 스택이 여기서도 주인공입니다.

Python 브라우저에서 실행

import random
from collections import deque

# DFS로 미로 자동 생성 — 스택으로 벽을 뚫으며 다닙니다
행수, 열수 = 8, 12
미로 = [[1] * 열수 for _ in range(행수)]

스택 = [(0, 0)]
미로[0][0] = 0
while 스택:
    ㄹ, ㅋ = 스택[-1]
    후보 = []
    for ㄷㄹ, ㄷㅋ in [(-2,0), (2,0), (0,-2), (0,2)]:
        ㄴㄹ, ㄴㅋ = ㄹ+ㄷㄹ, ㅋ+ㄷㅋ
        if 0 <= ㄴㄹ < 행수 and 0 <= ㄴㅋ < 열수 and 미로[ㄴㄹ][ㄴㅋ] == 1:
            후보.append((ㄴㄹ, ㄴㅋ, ㄹ+ㄷㄹ//2, ㅋ+ㄷㅋ//2))
    if 후보:
        ㄴㄹ, ㄴㅋ, ㅂㄹ, ㅂㅋ = random.choice(후보)
        미로[ㅂㄹ][ㅂㅋ] = 0            # 사이 벽을 뚫고
        미로[ㄴㄹ][ㄴㅋ] = 0            # 다음 칸으로
        스택.append((ㄴㄹ, ㄴㅋ))
    else:
        스택.pop()                      # 막다른 길 → 되돌아가기

for 줄 in 미로:
    print("".join("⬛" if ㅂ else "⬜" for ㅂ in 줄))
print()
print("↑ 실행할 때마다 다른 미로가 나옵니다. 스택 하나로 만들었어요.")

🤔 확인 문제

미로에서 좌표를 튜플 (행, 열) 로 다루는 이유는?

🤔 확인 문제

BFS로 도착점에 닿은 뒤 경로를 알아내는 방법은?

🤔 확인 문제

같은 미로를 BFS와 DFS로 각각 풀었을 때 확실히 말할 수 있는 것은?