15강 / 20강

BFS와 DFS — 넓게 퍼질까, 깊게 파고들까

큐 하나 vs 스택 하나, 그 한 글자 차이

그래프를 만들었으니 이제 돌아다녀야 합니다. 방법은 크게 둘이에요.

🌊 BFS · 너비 우선

연못에 돌을 던진 물결처럼
가까운 곳부터 한 겹씩
큐(FIFO) 사용
✅ 최단 거리를 보장

🕳️ DFS · 깊이 우선

미로에서 한 길로 끝까지
막히면 갈림길로 되돌아옴
스택(LIFO) 또는 재귀 사용
✅ 메모리를 적게 씀

놀라운 건, 두 코드가 거의 똑같다는 사실입니다. 꺼내는 자리를 popleft()로 하면 BFS, pop()으로 하면 DFS예요. 7강에서 배운 그 한 글자 차이가 알고리즘의 성격을 통째로 바꿉니다.

고등학생큐 하나 vs 스택 하나, 그 한 글자 차이

이 강의에서 가장 우아한 순간입니다.

같은 코드에서 자료구조 하나만 바꾸면 성격이 통째로 바뀐다

코드가 이렇습니다

대기 = [시작]
본곳 = {시작}
while 대기:
    현재 = 대기.pop(0)      # 앞에서 → 큐 → BFS
    # 현재 = 대기.pop()     # 뒤에서 → 스택 → DFS
    for 이웃 in 이웃들(현재):
        if 이웃 not in 본곳:
            본곳.add(이웃)
            대기.append(이웃)

꺼내는 곳	자료구조	성격
`pop(0)` 앞	큐	넓게 퍼진다
`pop()` 뒤	스택	깊게 판다

7강에서 배운 그 한 글자가 알고리즘을 바꾼다

왜 이렇게 되나

먼저 발견한 것을 먼저 볼지, 나중에 발견한 것을 먼저 볼지의 차이예요.

먼저 처리하는 것	결과
먼저 발견한 것 (큐)	가까운 곳부터
방금 발견한 것 (스택)	가던 방향으로 계속

"방금 본 것을 먼저" 하면 파고들게 된다

비유 — 도서관에서 자료 찾기

방식	비유
BFS	책 여러 권의 목차를 다 훑고 그다음 본문
DFS	한 권을 끝까지 읽고 다음 권

둘 다 전부 보지만 순서가 다르다

코드는 똑같고 popleft/pop 만 다릅니다. 실행해서 순서를 비교해 보세요.

Python 브라우저에서 실행

from collections import deque

친구 = {
    "민준": ["서연", "지호"],
    "서연": ["민준", "하윤"],
    "지호": ["민준", "예준"],
    "하윤": ["서연", "도윤"],
    "예준": ["지호"],
    "도윤": ["하윤"],
}

def 탐색(시작, 너비우선=True):
    본곳 = {시작}
    담을곳 = deque([시작])
    순서 = []
    while 담을곳:
        지금 = 담을곳.popleft() if 너비우선 else 담을곳.pop()   # ← 이 한 줄!
        순서.append(지금)
        for 이웃 in 친구[지금]:
            if 이웃 not in 본곳:
                본곳.add(이웃)
                담을곳.append(이웃)
    return 순서

print("BFS (큐):  ", " → ".join(탐색("민준", True)))
print("DFS (스택):", " → ".join(탐색("민준", False)))

고등학생'본 곳' 표시가 없으면 무한 루프

note 의 이 경고가 그래프 탐색의 필수 조건입니다.

14강에서 본 고리 때문이다 — 돌고 돈다

무슨 일이 벌어지나

A ↔ B 로 이어져 있다고 합시다.

단계	대기열
A 처리	[B]
B 처리 → A 를 넣는다	[A]
A 처리 → B 를 넣는다	[B]
…	영원히 ⚠

무향 그래프는 모든 선이 고리다 — 반드시 표시가 필요

언제 표시하느냐가 중요합니다

시점	결과
넣을 때 표시	대기열에 중복이 없다 ✔
꺼낼 때 표시	같은 것이 여러 번 들어간다 ⚠

넣을 때 표시하면 메모리도 시간도 아낀다

무엇으로 표시하나

방법	속도
집합 (set)	O(1) ✔
리스트	O(n) ⚠

4강의 집합이 왜 빠른가 가 여기서 결정적이 된다

리스트로 if x in 본곳 을 쓰면 탐색 전체가 몇 배 느려집니다.

비유 — 미로에 실 놓기

테세우스가 미로에 실을 놓았습니다. 왜였을까요?

실이 하는 일	설명
돌아오는 길	—
이미 온 곳 표시	같은 데를 안 돈다

표시가 없으면 영원히 헤맨다

🎮 격자 위에서 퍼지는 모습 보기

격자에서 시작점을 정하고 BFS와 DFS를 각각 눌러 보세요. BFS는 동심원처럼 퍼지고, DFS는 한 방향으로 쭉 뻗어 나갑니다. 칸에 적히는 숫자는 몇 번째로 방문했는지입니다.

BFS의 특권 — 최단 거리

BFS는 가까운 곳을 반드시 먼저 방문합니다. 그래서 어떤 점에 처음 도달한 순간, 그게 최단 거리임이 보장돼요. DFS는 이 보장이 없습니다 — 운 나쁘면 멀리 돌아서 도착합니다.

고등학생BFS 가 최단 경로를 주는 이유

BFS 에는 공짜 선물이 하나 있습니다.

BFS 로 처음 도달한 경로가 가장 짧은 경로다

왜 그런가

BFS 는 거리 순서대로 퍼지기 때문입니다.

순서	보는 것
1	시작점 (거리 0)
2	거리 1인 곳 전부
3	거리 2인 곳 전부

거리 2를 보기 전에 거리 1을 전부 봤다

그러니 어떤 곳에 처음 닿았다면 그보다 짧은 길이 있을 수가 없습니다.

있었다면 더 먼저 닿았을 테니까

DFS 는 그렇지 않습니다

	BFS	DFS
도달하나	한다	한다
최단인가	그렇다 ✔	아니다 ✗

DFS 는 먼 길로 빙 돌아 먼저 닿을 수 있다

비유 — 물결과 실뭉치

	비유
BFS	연못에 돌을 던진 물결 — 동심원으로 퍼진다
DFS	실뭉치를 한 방향으로 풀어 나간다

물결이 닿는 순서가 곧 거리 순서다

⚠ 단, 조건이 있습니다

모든 선의 비용이 같아야 합니다. 가중치가 있으면 BFS 로는 안 돼요.

가중치가 있으면 다익스트라 — 큐 대신 힙을 쓴다 (12강)

재미있죠. 또 자료구조 하나만 바뀝니다.

'몇 다리 건너 아는 사이'를 BFS로 계산합니다.

Python 브라우저에서 실행

from collections import deque

친구 = {
    "민준": ["서연", "지호"], "서연": ["민준", "하윤"],
    "지호": ["민준", "예준"], "하윤": ["서연", "도윤"],
    "예준": ["지호", "도윤"], "도윤": ["하윤", "예준"],
}

def 최단거리(시작):
    거리 = {시작: 0}
    부모 = {시작: None}
    ㄷ = deque([시작])
    while ㄷ:
        지금 = ㄷ.popleft()
        for 이웃 in 친구[지금]:
            if 이웃 not in 거리:
                거리[이웃] = 거리[지금] + 1
                부모[이웃] = 지금
                ㄷ.append(이웃)
    return 거리, 부모

거리, 부모 = 최단거리("민준")
for 사람, ㄱ in sorted(거리.items(), key=lambda ㅍ: ㅍ[1]):
    print(f"민준 → {사람:4} : {ㄱ}다리 건너")

# 부모를 거꾸로 따라가면 실제 경로가 나옵니다
목표 = "도윤"
길 = []
현재 = 목표
while 현재 is not None:
    길.append(현재); 현재 = 부모[현재]
print()
print("민준 → 도윤 경로:", " → ".join(reversed(길)))

DFS는 재귀로 쓰면 더 짧습니다

9강에서 재귀 = 스택이라고 했죠. DFS는 스택을 쓰니까, 스택을 직접 만드는 대신 재귀에게 맡기면 코드가 훨씬 짧아집니다.

DFS를 재귀 다섯 줄로. 파이썬이 스택을 대신 관리해 줍니다.

Python 브라우저에서 실행

친구 = {
    "민준": ["서연", "지호"], "서연": ["민준", "하윤"],
    "지호": ["민준", "예준"], "하윤": ["서연", "도윤"],
    "예준": ["지호"], "도윤": ["하윤"],
}

본곳 = set()
def dfs(지금, 깊이=0):
    본곳.add(지금)
    print("│  " * 깊이 + "└ " + 지금)
    for 이웃 in 친구[지금]:
        if 이웃 not in 본곳:
            dfs(이웃, 깊이 + 1)

dfs("민준")
print()
print("↑ 들여쓰기가 곧 스택의 깊이입니다 (9강)")

'서로 이어진 무리'를 세는 것도 탐색의 대표 응용입니다.

Python 브라우저에서 실행

from collections import deque

# 연결 요소 세기 — 섬이 몇 개인가?
그래프 = {
    "가": ["나"], "나": ["가"],           # 섬 1
    "다": ["라", "마"], "라": ["다"], "마": ["다"],   # 섬 2
    "바": [],                              # 섬 3 (외톨이)
}

본곳, 섬 = set(), 0
for 시작 in 그래프:
    if 시작 in 본곳:
        continue
    섬 += 1
    무리 = []
    ㄷ = deque([시작]); 본곳.add(시작)
    while ㄷ:
        지금 = ㄷ.popleft()
        무리.append(지금)
        for 이웃 in 그래프[지금]:
            if 이웃 not in 본곳:
                본곳.add(이웃); ㄷ.append(이웃)
    print(f"{섬}번째 무리: {무리}")

print(f"\n따로 노는 무리가 {섬}개 있습니다.")

고등학생언제 무엇을 쓸까

note 의 정리를 판단 기준으로 만들어 봅시다.

목적	고를 것
최단 경로 (가중치 없음)	BFS
가까운 것부터	BFS
모든 경우 시도	DFS
고리 찾기	DFS
연결돼 있나만	아무거나
메모리가 부족	DFS

마지막 줄이 실전에서 중요하다

메모리 차이

	대기열에 담기는 것
BFS	같은 층 전체 — 넓으면 어마어마
DFS	한 줄기만 — 깊이만큼

가지가 10개씩인 트리에서 20층이면 — BFS 는 10²⁰개

반대로 DFS 는 20개만 들고 있습니다.

DFS 의 약점

약점	설명
깊이 제한	재귀로 짜면 스택 오버플로 (9강)
최단이 아니다	먼 길로 갈 수 있다
무한히 깊으면	영영 안 돌아온다 ⚠

깊이가 무한할 수 있으면 DFS 를 쓰면 안 된다

비유 — 사람 찾기

상황	방법
근처에 있을 것 같다	주변부터 넓게 — BFS
어디든 있기만 하면 된다	한 방향으로 깊게 — DFS
사람이 적다	아무거나

"답이 어디쯤 있을까" 를 짐작하면 방법이 정해진다

🤔 확인 문제

BFS와 DFS 코드의 결정적 차이는?

해설 popleft()냐 pop()이냐 — 딱 한 곳만 다릅니다. 자료구조 선택이 알고리즘의 성격을 결정하는 가장 극적인 예예요.

🤔 확인 문제

미로에서 최소 걸음 수를 구해야 합니다. 무엇을 써야 할까요?

🤔 확인 문제

그래프 탐색에서 본곳 집합을 빠뜨리면?