Ch.7 그래프
면접실전 — 그래프 필수 4문제
면접관이 가장 좋아하는 그래프 문제 4선
그래프 챕터에서 배운 DFS, BFS, 위상정렬, Union-Find를 실전 문제에 적용해봅시다. 이 4문제만 마스터하면 그래프 면접의 80%를 커버합니다.
문제를 보면 '그래프인 줄 몰랐다'는 경우가 많다. 어떻게 판별할까?
2D 격자, 의존 관계, 복제, 연결성 — 이 키워드가 나오면 그래프를 떠올리세요.
핵심 개념
2D 격자 탐색
행렬을 그래프로 보고 상하좌우를 이웃으로 탐색
핵심 내용
가장 유명한 그래프 면접 문제, Number of Islands입니다
문제: 2D 격자에서 '1'(땅)로 연결된 섬의 개수를 구하라 핵심 아이디어: • '1'을 만나면 DFS로 연결된 모든 '1'을 방문 처리 • DFS 호출 횟수 = 섬의 개수 • 이전에 배운 연결 요소 개수 패턴과 동일!
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '0' # 방문 처리 (visited 대신)
dfs(r+1, c) # 상하좌우 탐색
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1 # DFS 1번 = 섬 1개
return count시간 O(M×N), 공간 O(M×N). `grid[r][c] = '0'`으로 visited 대신 원본을 수정하는 트릭!
그래프를 깊은 복사하라. 해시맵이 핵심입니다
# Definition: class Node:
# def __init__(self, val, neighbors=[]):
def cloneGraph(node):
if not node:
return None
old_to_new = {} # 원본 → 복사본 매핑
def dfs(node):
if node in old_to_new:
return old_to_new[node] # 이미 복사했으면 반환
copy = Node(node.val)
old_to_new[node] = copy # 매핑 등록
for neighbor in node.neighbors:
copy.neighbors.append(dfs(neighbor)) # 재귀 복사
return copy
return dfs(node)Clone Graph 패턴 1. `old_to_new` 해시맵으로 이미 복사한 노드 추적 2. 이미 복사했으면 바로 반환 (무한 루프 방지) 3. 복사 → 매핑 등록 → 이웃 재귀 복사
old_to_new가 visited 역할도 겸합니다. 사이클이 있어도 무한 루프에 빠지지 않습니다!
Course Schedule의 업그레이드 — 수강 순서까지 출력하라
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for crs, pre in prerequisites:
graph[pre].append(crs)
in_degree[crs] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))
# [0, 1, 2, 3] 또는 [0, 2, 1, 3]s7-5에서 배운 Kahn's Algorithm과 완전히 동일합니다. `order` 배열을 반환하느냐, `count == n` 을 반환하느냐 차이뿐!
2D 격자의 고급 문제 — 역방향 BFS 패턴
def pacificAtlantic(heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
pacific = set()
atlantic = set()
def dfs(r, c, visit, prev_height):
if (r, c) in visit:
return
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_height:
return
visit.add((r, c))
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
dfs(r+dr, c+dc, visit, heights[r][c])
# 태평양: 왼쪽+위쪽 가장자리에서 시작
for c in range(cols):
dfs(0, c, pacific, 0)
for r in range(rows):
dfs(r, 0, pacific, 0)
# 대서양: 오른쪽+아래쪽 가장자리에서 시작
for c in range(cols):
dfs(rows-1, c, atlantic, 0)
for r in range(rows):
dfs(r, cols-1, atlantic, 0)
return list(pacific & atlantic) # 교집합역방향 탐색 핵심 아이디어 • 모든 셀에서 바다까지 갈 수 있는지 확인 → O(M²×N²) 비효율 • 바다에서 역방향으로 도달 가능한 셀을 찾기 → O(M×N) 효율적 • 태평양 도달 셀 ∩ 대서양 도달 셀 = 정답
역방향 사고: "A에서 B로 갈 수 있는가?"를 "B에서 A로 갈 수 있는가?"로 뒤집으면 효율적!
문제에서 그래프를 알아보는 시그널 키워드를 정리합니다
그래프 문제 시그널 🔹 "연결된", "도달 가능한" → DFS/BFS 🔹 "최단 거리", "최소 이동" → BFS 🔹 "순서", "선수 조건" → 위상정렬 🔹 "같은 그룹", "합치기" → Union-Find 🔹 "2D 격자", "섬" → DFS/BFS (상하좌우)
2D 격자 문제는 그래프인 줄 모르고 넘어가는 경우가 많습니다. 격자 = 그래프입니다!
Number of Islands에서 DFS 호출 횟수의 의미는?
Clone Graph에서 old_to_new 해시맵은 visited 역할도 겸한다
그래프 면접 준비 완료!
정리 노트
그래프 필수 4문제
문제별 핵심 패턴
- Number of Islands
- 2D 격자 DFS — DFS 호출 횟수 = 섬 수
- Clone Graph
- old_to_new 해시맵 — visited 겸용
- Course Schedule
- Kahn's Algorithm — 위상정렬 + 사이클 감지
- Pacific Atlantic
- 역방향 DFS — 바다에서 출발, 교집합
판별 키워드
- 연결/도달
- → DFS/BFS
- 최단/최소
- → BFS
- 순서/의존
- → 위상정렬
- 그룹/합치기
- → Union-Find
2D 격자를 보면 '이것은 그래프다'라고 먼저 인식하기!
시각 자료
핵심 정리
- 1Number of Islands: 2D DFS, 연결 요소 패턴
- 2Clone Graph: 해시맵 DFS, visited 겸용
- 3Course Schedule: 위상정렬, 사이클 감지
- 4Pacific Atlantic: 역방향 DFS, 교집합
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작