초보자를 위한 LeetCode 그래프 문제 연습 방법: 구조화된 로드맵
Source: Dev.to
TL;DR
- 무작위 그래프 문제부터 시작하지 말고 그리드와 간단한 트리에서 가중치 없는 BFS/DFS부터 시작한 뒤, 인접 리스트, 위상 정렬, 최단 경로 순으로 진행하세요.
- 패턴별 클러스터(BFS, DFS, 연결 요소, 위상 정렬, 최단 경로)로 그래프를 연습하고, 문제를 여기저기 뛰어다니지 마세요. 그래야 뇌가 공통 구조를 인식할 수 있습니다.
- 코딩하기 전에 시각적 다이어그램(노드, 엣지, 레벨)을 사용해 그래프 동작을 추론하세요. 특히 BFS 레벨과 사이클 탐지에 유용합니다.
- 초보자는 기본 그리드/그래프 모델링을 건너뛰고, 그림을 그리지 않으며, 너무 일찍 Dijkstra/Union‑Find 로 넘어가 버리는 경우가 많아 자신감과 기억력이 떨어집니다.
- 간단한 3단계 로드맵을 DSA 학습 경로와 AI‑가이드 LeetCode 연습(AI‑guided LeetCode practice) 같은 도구와 함께 활용하면 그래프 문제를 혼란스럽기보다 체계적으로 느낄 수 있습니다.
Phase 0: Get Comfortable with the Mental Model of a Graph
What is a graph?
핵심적으로 그래프는 다음과 같습니다:
- 노드(정점)들의 집합.
- 엣지(간선)들의 집합, 노드를 연결함(방향이 있을 수도 있음).
시각적 예시
A ---- B
| |
| |
C ---- D많은 LeetCode 문제를 그래프로 모델링할 수 있습니다:
- 그리드(각 셀을 이웃과 연결된 노드로 간주).
- 강의 선수 조건(노드 = 강의, 엣지 = “선수 강의”).
- 소셜 네트워크, 도시 지도, 의존성 그래프 등.
Minimal code representation
대부분의 초급 문제에서는 인접 리스트가 충분합니다:
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # if undirected이 정도에 익숙해지면 나머지 그래프 알고리즘은 훨씬 쉬워집니다.
Phase 1: Grids and Trees – Your Gentle Graph On‑Ramp
1A. Grids as implicit graphs
**“Number of Islands”**나 “Rotting Oranges” 같은 문제는 변장한 그래프 문제입니다:
- 각 셀
(r, c)이 하나의 노드가 됩니다. - 유효한 경우 상하좌우 이웃과 엣지로 연결됩니다.
이웃 헬퍼
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbors(r, c, rows, cols):
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
yield nr, nc중점:
- 노드를 방문 처리하기.
- 재방문을 방지하기.
- BFS가 레이어별로 탐색하는 방식을 이해하기.
1B. Trees as simpler graphs
이진 트리 문제는 “구조가 정해져 있고 사이클이 없는 그래프”라고 볼 수 있습니다.
연습 내용:
- 깊이, 경로 합, 서브트리 검증 등에 DFS(재귀·반복) 사용.
- 거리, 레벨별 평균 등에 BFS(레벨 순회) 사용.
Phase 1 목표
그리드와 트리에서 BFS/DFS를 주저 없이 구현할 수 있고, 노트에 깔끔하고 재사용 가능한 순회 템플릿을 갖추는 것입니다.
Phase 2: Explicit Graphs – Adjacency Lists, Components, and Cycles
2A. Build the graph yourself
n개의 노드와 edges 리스트가 주어졌을 때:
def build_graph(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # if undirected
return graph다음과 같은 문제를 풀어보세요:
- “연결 요소는 몇 개인가?”
- “이 그래프는 이분 그래프인가?”
- “X와 Y 사이에 경로가 존재하는가?”
2B. Connected components with DFS/BFS
모든 노드를 순회하면서 아직 방문하지 않은 노드가 나오면 BFS/DFS를 시작해 도달 가능한 모든 노드를 표시하고, 컴포넌트 수를 증가시킵니다.
시각적 예시
Component 1: 0 - 1 - 2
Component 2: 3 - 4
Component 3: 52C. Cycle detection
- 무방향 그래프 –
parent파라미터를 갖는 DFS; 부모가 아닌 방문된 이웃을 만나면 사이클이 존재합니다. - 방향 그래프 – 3색(미방문, 방문중, 방문완료) DFS 또는 재귀 스택 집합을 사용합니다.
이 단계가 “그냥 순회만 하는 문제”를 넘어서는 첫 걸음입니다.
Phase 3: Topological Sort and Shortest Paths
3A. Topological sort (ordering with prerequisites)
두 가지 흔한 접근법:
- Kahn 알고리즘(진입 차수를 이용한 BFS 기반).
- DFS + 스택(역후위 순서).
전형적인 패턴: 노드 = 작업/강의, 엣지 u → v는 “u가 v보다 먼저 수행돼야 함”을 의미합니다. 위상 정렬은 의존 관계를 만족하는 모든 순서 중 하나입니다.
더 많은 면접 준비 팁은 how to run mock coding interviews by yourself를 참고하세요.
3B. Shortest paths in unweighted graphs
BFS 사용: 모든 엣지 비용이 1이므로, 출발점에서 BFS를 하면 최소 이동 횟수가 자연스럽게 구해집니다. 예시: 가중치가 없는 그리드에서 최단 경로 찾기.
3C. Shortest paths with weights (optional for beginners)
BFS/DFS와 위상 정렬에 익숙해진 뒤 Dijkstra 알고리즘(최소 힙 사용)을 배웁니다. 대부분의 인터뷰에서는 모든 가중치 최단 경로 변형을 알 필요는 없지만, BFS로 충분한 경우와 Dijkstra가 필요한 경우를 구분할 수 있어야 합니다.
Weekly Practice Plan for Graph Beginners
전체 DSA 학습 경로에 맞춰 현실적인 3~4주 계획입니다.
Week 1 – Grids & Trees
- 3~4개의 “Number of Islands” 스타일 그리드 문제.
- 2~3개의 트리 BFS 문제(레벨 순회, 레벨별 평균 등).
- 2~3개의 트리 DFS 문제(최대 깊이, 경로 합 등).
Week 2 – Explicit Graphs & Components
- 인접 리스트를 직접 만들고 순회하는 문제 3개.
- 연결 요소 개수 세기 문제 2개.
- 무방향 그래프에서 사이클 탐지 문제 2개.
Week 3 – Directed Graphs & Toposort
- 방향 그래프에서 사이클 탐지 문제 2~3개.
- 위상 정렬을 이용한 코스 스케줄/작업 순서 문제 2~3개.
- 무가중 그래프에서 BFS 최단 경로 문제 1~2개.
Optional Week 4 – Weighted Graphs
- 가중치가 있는 Dijkstra 스타일 문제 2~3개.
- 그래프와 다른 패턴을 결합한 문제 1~2개.
AI‑guided LeetCode practice 같은 도구를 활용하면 맞춤형 문제 세트를 자동 생성하고 즉시 피드백을 받을 수 있어, 이 로드맵을 따라가면서 효율적으로 실력을 키울 수 있습니다.