통합 요약노트
Ch.7 그래프
DFS, BFS, 위상 정렬, Union-Find — 연결 관계 탐색의 핵심
이 챕터의 내용
그래프란? — 노드, 엣지, 방향/무방향, 가중치
트리는 '부모→자식' 단방향 계층이지만, 그래프는 아무 노드끼리나 자유롭게 연결됩니다.
자료구조의 최종 보스, 그래프를 만나봅시다
배열, 링크드 리스트, 트리… 지금까지 배운 자료구조를 떠올려보세요
이것들은 모두 그래프의 특수한 형태입니다. 링크드 리스트는 일렬 그래프, 트리는 사이클 없는 그래프
- 그래프 = 노드 + 엣지로 이루어진 가장 일반적인 연결 구조
- 방향/무방향, 가중치 여부로 종류가 나뉜다
- 파이썬 딕셔너리로 인접 리스트 표현이 기본
그래프 표현 — 인접 리스트 vs 인접 행렬
희소 그래프는 인접 리스트, 밀집 그래프는 인접 행렬이 유리합니다. 면접에서 이 판단이 중요합니다.
면접에서 가장 많이 쓰는 그래프 표현법을 배웁니다
defaultdict(list)는 그래프 면접의 필수 패턴입니다. `graph[node].append(neighbor)` 한 줄이면 끝!
방향 그래프라면? `graph[v].append(u)` 줄만 빼면 됩니다
- 인접 리스트: defaultdict(list)로 O(V+E) 공간
- 인접 행렬: V×V 배열로 O(1) 연결 확인
- 면접 90%는 인접 리스트 — 희소 그래프가 대부분
DFS — 깊이 우선 탐색, 끝까지 파고들기
스택(또는 재귀 호출 스택)이 되돌아갈 위치를 기억하고, visited 집합이 재방문을 막습니다.
그래프 탐색의 기본 무기, DFS를 배웁니다
DFS는 한 길을 끝까지 가봅니다. 막히면 돌아와서 다른 길을 시도합니다
DFS의 핵심 규칙: 더 깊이 갈 수 있으면 가고, 못 가면 되돌아간다
- DFS = 한 길을 끝까지 탐색 후 되돌아가기
- 재귀 DFS 4줄 패턴은 반드시 암기
- visited 없으면 무한 루프, DFS 호출 횟수 = 연결 요소 수
BFS — 너비 우선 탐색, 최단거리의 열쇠
한 겹씩 탐색하기 때문에 처음 도착한 경로가 곧 최단 경로입니다. 이것이 BFS의 핵심 강점입니다.
최단거리를 구하는 가장 확실한 무기, BFS
DFS는 스택(LIFO) → 깊이 우선 BFS는 큐(FIFO) → 너비 우선
"최단"이라는 키워드가 보이면 99% BFS입니다!
- BFS = 큐(FIFO)로 가까운 순서대로 탐색
- 가중치 없는 그래프에서 BFS = 최단거리
- deque.popleft() O(1) vs list.pop(0) O(n)
위상정렬 — 선수과목부터 들어라!
사이클이 있으면 위상정렬이 불가능합니다. 이것이 바로 'Course Schedule' 문제의 핵심입니다.
순서가 있는 작업을 정렬하는 위상정렬을 배웁니다
진입차수가 0인 노드 = 선행 조건이 없는 노드. 이 노드부터 처리를 시작합니다
위상정렬은 DAG(사이클 없는 방향 그래프)에서만 가능합니다. 사이클이 있으면 정렬 불가!
- 위상정렬 = 선행 조건을 지키며 모든 노드 정렬
- Kahn's Algorithm: 진입차수 0 → BFS → 진입차수 감소
- Course Schedule = 사이클 감지 문제
Union-Find — 같은 편인지 묻는 자료구조
트리 구조로 각 그룹을 표현하면, find 연산으로 거의 O(1)에 같은 그룹인지 판별합니다.
그룹을 합치고 판별하는 Union-Find를 배웁니다
처음에는 모든 노드가 자기 자신이 대표입니다. union하면 한쪽 대표가 다른 쪽 아래로 들어갑니다
같은 그룹 판별: `find(x) == find(y)` — 루트가 같으면 같은 그룹!
- Union-Find = 그룹 합치기(union) + 그룹 판별(find)
- 경로 압축 + 랭크 합치기로 거의 O(1)
- 연결 요소, 사이클 감지에 활용
면접실전 — 그래프 필수 4문제
2D 격자, 의존 관계, 복제, 연결성 — 이 키워드가 나오면 그래프를 떠올리세요.
가장 유명한 그래프 면접 문제, Number of Islands입니다
시간 O(M×N), 공간 O(M×N). `grid[r][c] = '0'`으로 visited 대신 원본을 수정하는 트릭!
그래프를 깊은 복사하라. 해시맵이 핵심입니다
- Number of Islands: 2D DFS, 연결 요소 패턴
- Clone Graph: 해시맵 DFS, visited 겸용
- Course Schedule: 위상정렬, 사이클 감지
- Pacific Atlantic: 역방향 DFS, 교집합
챕터7 종합퀴즈 — 그래프 완전 정복
문제의 키워드를 보고 자동으로 알고리즘을 선택할 수 있다면, 그래프 마스터입니다.
무방향 그래프에서 노드 A와 B를 연결할 때, 인접 리스트에 추가해야 하는 횟수는?
노드 V개, 엣지 E개인 그래프에서 인접 리스트의 공간 복잡도는?
가중치가 없는 그래프에서 A에서 B까지 최단 거리를 구하려면?
- 그래프 = 노드 + 엣지, 인접 리스트가 기본 표현
- DFS(스택/재귀) + BFS(큐) = 탐색의 양대 무기
- 위상정렬: 순서 문제 + 사이클 감지
- Union-Find: 그룹 합치기/판별을 거의 O(1)로
- 면접 필수 4문제를 패턴으로 암기
핵심 용어 모음
노드(Vertex)
그래프의 꼭짓점, 데이터를 담는 단위
엣지(Edge)
두 노드를 연결하는 선
방향 그래프
A→B는 되지만 B→A는 안 될 수 있음
무방향 그래프
A-B 연결이면 양쪽 모두 이동 가능
인접 리스트
각 노드마다 이웃 목록을 저장하는 방식
인접 행렬
V×V 2차원 배열로 연결 여부를 표시
defaultdict(list)
없는 키에 자동으로 빈 리스트 생성
DFS
Depth-First Search — 깊이 우선 탐색
스택/재귀
DFS의 핵심 자료구조 — 되돌아갈 위치 기억
visited
이미 방문한 노드를 기록하는 set
BFS
Breadth-First Search — 너비 우선 탐색
큐(Queue)
FIFO — 먼저 넣은 것을 먼저 꺼냄
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기