15강 / 20강

BFS와 DFS — 관계망을 훑는 두 가지 방법

"이 상품과 2단계 안에 연결된 상품" 을 찾아라

14강에서 만든 '함께 구매' 그래프가 있습니다. 이제 진짜 문제를 풀어 봅시다.

"이어폰 상세 페이지에 추천 상품을 띄우려고 합니다. 직접 함께 산 상품뿐 아니라, 2단계까지 연결된 상품도 넣어 주세요. 단, 가까운 것부터 순서대로요."

이 요구를 그대로 구현하는 알고리즘이 BFS(너비 우선 탐색)입니다.

고등학생넓게 훑을까 깊게 파고들까

그래프를 훑는 방법이 둘 있습니다. 그리고 자료구조 하나 차이예요.

	BFS (너비 우선)	DFS (깊이 우선)
방식	가까운 것부터	한 길로 끝까지
자료구조	큐	스택
비유	물결이 퍼지듯	미로에서 한 길로

11강의 큐와 스택이 여기서 쓰인다

비유 — 친구 찾기

어떤 사람을 SNS 에서 찾습니다.

BFS — 내 친구를 전부 보고, 그다음 친구의 친구를 전부
DFS — 친구 한 명을 잡고 그 사람의 친구의 친구의… 끝까지

BFS 는 가까운 사람부터, DFS 는 한 갈래를 끝까지

어느 걸 언제 쓰나

물음	쓸 것
가장 가까운 것은?	BFS — 가까운 것부터 보니까
최단 경로	BFS
연결됐나만 확인	둘 다 OK
모든 경로 찾기	DFS
메모리가 부족	DFS — 덜 쓴다

"이 상품과 2단계 안에 연결된 것" → BFS

BFS vs DFS — 한 줄 요약

	BFS (너비 우선)	DFS (깊이 우선)
훑는 순서	가까운 곳부터 한 겹씩	한 길로 끝까지 갔다가 되돌아옴
쓰는 도구	큐 (11강)	스택 또는 재귀
비유	연못에 돌 던졌을 때 퍼지는 물결	미로에서 벽 짚고 가기
잘하는 일	최단 거리 · N단계 이내 찾기	모든 경로 탐색 · 사이클 찾기
쇼핑몰에서	추천 · 촌수 · 최소 배송 경유	카테고리 전개 · 의존성 추적

고등학생BFS vs DFS — 한 줄 요약

note 의 한 줄이 정확합니다. 조금만 더 풀어 볼게요.

코드가 거의 같다 — 큐냐 스택이냐만 다르다

공통 뼈대

시작점을 담는다
하나 꺼낸다
가 본 적 없으면 표시하고 처리
이웃을 담는다
빌 때까지 2~4 반복

2번에서 어디서 꺼내느냐만 다르다

꺼내는 곳	결과
앞에서 (큐)	BFS
뒤에서 (스택)	DFS

3번의 '가 본 적 없으면' 이 중요합니다

14강의 순환 문제를 막는 장치예요.

방문 표시가 없으면 영원히 돈다

그리고 방문 표시는 집합으로 합니다(9강). 확인이 O(1) 이어야 하니까요.

지금까지 배운 게 다 쓰입니다

부품	어느 강
큐 · 스택	11강
집합 (방문 표시)	9강
인접 리스트	14강
반복문	2강

알고리즘은 부품의 조합이다

BFS의 핵심은 '큐'와 '방문 기록' 두 가지뿐입니다.

Python 브라우저에서 실행

from collections import deque

함께구매 = {
    "이어폰":   ["케이스", "충전기"],
    "케이스":   ["이어폰", "필름", "스트랩"],
    "충전기":   ["이어폰", "케이블", "멀티탭"],
    "필름":     ["케이스"],
    "스트랩":   ["케이스"],
    "케이블":   ["충전기"],
    "멀티탭":   ["충전기"],
}

def bfs(그래프, 시작, 최대단계=2):
    방문 = {시작: 0}
    큐 = deque([시작])
    결과 = []
    while 큐:
        현재 = 큐.popleft()            # ← 큐: 먼저 넣은 것부터
        단계 = 방문[현재]
        if 단계 >= 최대단계:
            continue
        for 이웃 in 그래프.get(현재, []):
            if 이웃 not in 방문:        # 이미 본 곳은 건너뛴다 (순환 방지)
                방문[이웃] = 단계 + 1
                결과.append((이웃, 단계 + 1))
                큐.append(이웃)
    return 결과

print("🎧 이어폰 페이지 추천 상품")
for 상품, 단계 in bfs(함께구매, "이어폰", 최대단계=2):
    표시 = "함께 산 상품" if 단계 == 1 else "이런 상품도 봤어요"
    print(f"   {단계}단계  {상품:<6} ({표시})")

같은 그래프를 DFS로 훑으면

DFS는 큐 대신 스택을 씁니다. 딱 그 한 글자 차이인데 훑는 순서가 완전히 달라져요.

popleft() 를 pop() 으로 바꾸면 BFS가 DFS가 됩니다.

Python 브라우저에서 실행

함께구매 = {
    "이어폰":   ["케이스", "충전기"],
    "케이스":   ["이어폰", "필름", "스트랩"],
    "충전기":   ["이어폰", "케이블", "멀티탭"],
    "필름": ["케이스"], "스트랩": ["케이스"],
    "케이블": ["충전기"], "멀티탭": ["충전기"],
}

def dfs(그래프, 시작):
    방문, 순서 = set(), []
    스택 = [시작]
    while 스택:
        현재 = 스택.pop()              # ← 스택: 마지막에 넣은 것부터
        if 현재 in 방문:
            continue
        방문.add(현재)
        순서.append(현재)
        for 이웃 in reversed(그래프.get(현재, [])):
            if 이웃 not in 방문:
                스택.append(이웃)
    return 순서

def dfs재귀(그래프, 현재, 방문=None, 순서=None):
    방문 = set() if 방문 is None else 방문
    순서 = [] if 순서 is None else 순서
    방문.add(현재); 순서.append(현재)
    for 이웃 in 그래프.get(현재, []):
        if 이웃 not in 방문:
            dfs재귀(그래프, 이웃, 방문, 순서)
    return 순서

print("DFS (스택):", " → ".join(dfs(함께구매, "이어폰")))
print("DFS (재귀):", " → ".join(dfs재귀(함께구매, "이어폰")))
print()
print("💡 재귀는 파이썬이 대신 스택을 관리해 주는 것뿐, 원리는 같습니다.")

🎮 추천 확산 시뮬레이터

상품 하나를 클릭하면 관계망을 따라 추천이 퍼져 나갑니다. BFS는 동심원처럼, DFS는 뱀처럼 움직이는 걸 보세요. 단계 제한을 바꿔 가며 추천 개수가 어떻게 폭발하는지도 확인해 보세요.

고등학생추천이 폭발하는 문제

note 가 실무의 함정을 짚습니다. 추천 시스템에서 자주 나는 사고예요.

2단계만 가도 수만 개가 나온다

왜 폭발하나

상품 하나가 50개와 연결되어 있다고 합시다.

단계	상품 수
1단계	50
2단계	2,500
3단계	125,000

한 단계마다 곱해진다 — 12강의 2ⁿ 과 같은 폭발

그리고 인기 상품이 문제입니다

거의 모든 사람이 사는 상품이 있습니다 — 생수, 건전지 같은 거요.

그러면 그 상품이 거의 모든 것과 연결됩니다. 거기를 지나면 그래프 전체로 퍼져요.

허브 하나가 모든 것을 이어 버린다

그래서 하는 일

대책	설명
단계 제한	2단계까지만
인기 상품 제외	너무 흔한 연결은 뺀다
가중치 문턱	몇 번 이상 함께 산 것만
개수 제한	상위 N개만 (10강)

연결이 많다고 다 쓰면 추천이 무의미해진다

모든 상품이 추천되면 추천이 아니죠. 줄이는 것이 추천의 본질입니다.

BFS가 최단 거리를 보장하는 이유

BFS는 거리 1인 곳을 전부 본 다음에 거리 2로 넘어갑니다. 그래서 어떤 점에 처음 도달했을 때의 거리가 곧 최단 거리예요.

DFS는 이 보장이 없습니다. 운 나쁘면 먼 길로 먼저 도달할 수 있어요.

단, 이 보장은 간선의 비용이 모두 같을 때만 유효합니다. 배송비처럼 간선마다 비용이 다르면 다익스트라 알고리즘을 써야 하는데, 그건 BFS의 큐를 우선순위 큐로 바꾼 것입니다 — 11강에서 배운 그 힙이에요.

다익스트라 = BFS + 우선순위 큐. 8줄이면 됩니다.

Python 브라우저에서 실행

import heapq

# 배송망 — 간선마다 비용이 다르다
배송망 = {
    "서울": [("대전", 3000), ("강릉", 5000)],
    "대전": [("서울", 3000), ("대구", 2000), ("광주", 3500)],
    "대구": [("대전", 2000), ("부산", 1500)],
    "광주": [("대전", 3500), ("부산", 4000)],
    "강릉": [("서울", 5000), ("대구", 6000)],
    "부산": [("대구", 1500), ("광주", 4000), ("제주", 8000)],
    "제주": [("부산", 8000)],
}

def 최저비용(그래프, 시작):
    거리 = {시작: 0}
    힙 = [(0, 시작)]                     # ← 큐 대신 우선순위 큐
    while 힙:
        비용, 현재 = heapq.heappop(힙)    # 가장 싼 곳부터 확정
        if 비용 > 거리.get(현재, float("inf")):
            continue
        for 이웃, w in 그래프[현재]:
            새비용 = 비용 + w
            if 새비용 < 거리.get(이웃, float("inf")):
                거리[이웃] = 새비용
                heapq.heappush(힙, (새비용, 이웃))
    return 거리

for 도시, 비용 in sorted(최저비용(배송망, "서울").items(), key=lambda x: x[1]):
    print(f"  서울 → {도시:<4} {비용:>6,}원")

print()
print("💡 BFS의 큐를 힙으로 바꾸면 다익스트라. 알고리즘은 이렇게 이어집니다.")

고등학생무한 반복을 막는 법

15강을 마치며 가장 중요한 실수를 정리합시다.

방문 표시를 언제 하느냐

두 가지 방법이 있는데 하나가 위험합니다

언제 표시	결과
담을 때	안전 ✔
꺼낼 때	같은 게 여러 번 담긴다

꺼낼 때 표시하면 큐가 부풀어 오른다

왜 그런가

A 의 이웃이 C 이고 B 의 이웃도 C 라면 — A 를 처리할 때 C 를 담고, B 를 처리할 때 또 담습니다.

C 를 꺼낼 때 표시하면 이미 두 번 담긴 뒤예요.

틀린 답은 아니지만 메모리와 시간을 낭비한다

비유 — 초대장

파티에 초대할 때 보내면서 명단에 표시하는 것과 온 사람을 표시하는 것.

두 번째면 같은 사람에게 초대장이 여러 장 갑니다. 오는 건 한 번인데 우편비가 낭비되죠.

중복을 들어올 때 막아야 한다

그리고 이건 흔한 면접 문제입니다

BFS 를 짤 줄 아느냐보다 이 세부를 아느냐 를 묻습니다. 동작하는 코드와 제대로 된 코드의 차이니까요.

🤔 확인 문제

"이 상품과 2단계 이내로 연결된 상품을 가까운 순서로" — 적합한 알고리즘은?

🤔 확인 문제

BFS 코드에서 큐.popleft() 를 스택.pop() 으로 바꾸면?

🤔 확인 문제

배송비처럼 간선마다 비용이 다른 그래프에서 최소 비용 경로를 찾으려면?