13강: 그래프 표현

이 강의에서 배우는 것

• 1인접 리스트와 인접 행렬의 장단점을 설명하고 상황에 맞게 선택한다.
• 2방향/무방향, 가중/비가중 그래프를 코드로 표현한다.
• 3백준 스타일 입력(N 노드, M 간선)을 올바르게 파싱한다.

개요

소개: 그래프가 등장하는 백준 문제 유형들

그래프는 현실의 수많은 관계를 모델링합니다.

모든 그래프 문제의 첫 번째 단계는 **그래프를 올바르게 표현**하는 것입니다.

핵심 개념

인접 리스트 (Adjacency List)

그래프:
  1 ─── 2
  │     │
  3 ─── 4

인접 리스트:
  1: [2, 3]
  2: [1, 4]
  3: [1, 4]
  4: [2, 3]

• 공간: **O(V + E)**
• 특정 간선 존재 여부: O(degree) — 선형 탐색 필요
• 모든 인접 노드 탐색: O(degree) — 효율적
• **대부분의 그래프 문제에서 기본 선택**

인접 행렬 (Adjacency Matrix)

그래프:
  1 ─── 2
  │
  3

인접 행렬 (V=4):
     1  2  3  4
  1 [0, 1, 1, 0]
  2 [1, 0, 0, 0]
  3 [1, 0, 0, 0]
  4 [0, 0, 0, 0]

• 공간: **O(V²)**
• 특정 간선 존재 여부: **O(1)**
• 모든 인접 노드 탐색: O(V)
• V ≤ 1000 이고 밀집 그래프(E ≈ V²)일 때 유리

공간 복잡도 비교

text-art 그래프 예시

방향 그래프 (Directed):
  ┌── 1 ──→ 2
  │         │
  │         ↓
  └──→ 3 ──→ 4

무방향 그래프 (Undirected):
  1 ─── 2
  │     │
  3 ─── 4 ─── 5

가중 그래프 (Weighted):
  1 ──5── 2
  │       │
  3       7
  │
  2 ──── 3 ──1── 4

예제로 보기

자주 하는 실수 5가지

1. **1-indexed vs 0-indexed 혼동** - 백준 문제는 대부분 노드 번호가 1부터 시작 - `graph = [[] for _ in range(n + 1)]` — 인덱스 1~n 사용 - 0번 인덱스는 사용하지 않음
2. **무방향 그래프에서 간선을 한 방향만 추가** ```python # 잘못된 코드 graph[u].append(v) # u→v 만 추가 # 올바른 코드 graph[u].append(v) graph[v].append(u) # 양방향 모두 추가 ```
3. **인접 행렬 크기를 n+1이 아닌 n으로 설정** - 1-indexed이면 `graph[n][n]` → `graph[n+1][n+1]`
4. **가중 그래프에서 0 가중치를 연결 없음으로 착각** - 인접 행렬에서 0은 보통 "연결 없음" 의미 - 0 가중치 간선이 있다면 `float('inf')` 를 초기값으로 사용
5. **자기 루프(self-loop) 처리 누락** - `u == v` 인 간선 입력이 올 때 무방향이면 한 번만 추가

정리

직접 해 보기

1. 위의 text-art 그래프를 인접 리스트로 코드에 표현하세요.
2. 같은 그래프를 인접 행렬로도 표현하세요.
3. V=5, E=7 인 무방향 그래프에서 인접 리스트와 인접 행렬의 메모리 사용량을 계산하세요.

과제

`homework/README.md` 참조