4. 그래프 표현 (Graph Representation) — 인접 행렬 / 인접 리스트

핵심 인사이트 (3줄 요약)

1. 본질: 그래프 (Graph)는 정점 (Vertex)과 간선 (Edge)으로 이루어진 자료구조이며, 인접 행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List) 두 가지 방식으로 컴퓨터에 표현한다.
2. 가치: 인접 행렬은 O(1) 간선 조회, 인접 리스트는 O(V+E) 공간 효율 — 알고리즘과 그래프 밀도에 따라 올바른 표현을 선택해야 성능을 끌어낼 수 있다.
3. 판단 포인트: 밀집 그래프 (Dense Graph, E ≈ V²)에는 인접 행렬, 희소 그래프 (Sparse Graph, E ≪ V²)에는 인접 리스트가 기본 선택 기준이다.

Ⅰ. 개요 및 필요성

그래프 (Graph)는 G = (V, E)로 정의되며, V는 정점 집합, E는 간선 집합이다. 실세계의 네트워크, 지도, 소셜 관계, 의존성 등 수많은 문제가 그래프로 모델링된다.

그래프의 주요 분류:

📢 섹션 요약 비유: 그래프는 도시들(정점)과 도로들(간선)로 구성된 지도다. 표현 방식은 이 지도를 어떤 형식의 종이에 기록하느냐의 차이다.

Ⅱ. 아키텍처 및 핵심 원리

예시 그래프

정점: {A, B, C, D, E}
간선: {A-B, A-C, B-D, C-D, D-E}

     A
    / \
   B   C
    \ /
     D
     |
     E

인접 행렬 (Adjacency Matrix)

V×V 크기의 2차원 배열. adj[i][j] = 1이면 i→j 간선 존재.

     A  B  C  D  E
  A [0, 1, 1, 0, 0]
  B [1, 0, 0, 1, 0]
  C [1, 0, 0, 1, 0]
  D [0, 1, 1, 0, 1]
  E [0, 0, 0, 1, 0]

가중치 그래프는 adj[i][j] = 가중치 (없는 경우 ∞ 또는 0).

인접 리스트 (Adjacency List)

각 정점마다 연결된 정점 목록을 저장.

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C, E]
E: [D]

ASCII 다이어그램 — 두 표현 방식 비교

┌──────────────────────────────────────────────────────────┐
│  [인접 행렬]              [인접 리스트]                    │
│                                                          │
│    A B C D E             A ──→ [B] ──→ [C]              │
│  A[0 1 1 0 0]            B ──→ [A] ──→ [D]              │
│  B[1 0 0 1 0]            C ──→ [A] ──→ [D]              │
│  C[1 0 0 1 0]            D ──→ [B] ──→ [C] ──→ [E]      │
│  D[0 1 1 0 1]            E ──→ [D]                      │
│  E[0 0 0 1 0]                                            │
│                                                          │
│  공간: O(V²)             공간: O(V+E)                     │
│  간선 조회: O(1)          간선 조회: O(degree)             │
└──────────────────────────────────────────────────────────┘

간선 리스트 (Edge List)

모든 간선을 (u, v, weight) 튜플로 저장.

[(A,B,1), (A,C,1), (B,D,1), (C,D,1), (D,E,1)]

크루스칼 (Kruskal) 알고리즘처럼 간선 정렬이 필요한 경우에 적합.

표현 방식별 복잡도 비교

📢 섹션 요약 비유: 인접 행렬은 전국 도로 연결표 (모든 도시 쌍에 대해 O/X 표시), 인접 리스트는 각 도시의 관광 안내서 (이 도시에서 갈 수 있는 곳 목록)다.

Ⅲ. 비교 및 연결

밀집 vs 희소 그래프에서의 선택

V=1,000, E=200 (희소, E ≪ V²=1,000,000)
  → 인접 행렬: 1,000,000 셀 메모리 낭비
  → 인접 리스트: 1,200개 항목으로 충분

V=1,000, E=900,000 (밀집, E ≈ V²)
  → 인접 리스트: 900,000개 포인터 오버헤드
  → 인접 행렬: 1,000,000 셀로 O(1) 접근 효율적

방향/무방향 그래프 처리 차이

📢 섹션 요약 비유: 방향 그래프는 일방통행 도로, 무방향 그래프는 양방향 도로다. 인접 행렬에서 방향 그래프는 비대칭 행렬, 무방향은 대칭 행렬로 표현된다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 소셜 네트워크 팔로워 관계 (V=억, E=수십억)

• 희소 그래프 → 인접 리스트 필수
• 인접 행렬 시 V²=10^16 셀 → 물리적 불가

시나리오 2: 플로이드-워샬 (Floyd-Warshall) 전체 쌍 최단 경로

• O(V³) 알고리즘 → 인접 행렬로 O(1) 간선 비용 조회 최적화
• 인접 리스트라면 간선 조회마다 O(degree) 추가 비용

시나리오 3: DFS (Depth-First Search) / BFS (Breadth-First Search)

• 정점의 이웃 순회가 핵심 → 인접 리스트가 O(V+E)로 효율적
• 인접 행렬 사용 시 이웃 순회에 O(V) → 전체 DFS O(V²) 비효율

기술사 판단 기준

📢 섹션 요약 비유: 그래프 표현 선택은 수납 방식 선택과 같다. 물건이 가득 찬 서랍(밀집)은 표 형식이 낫고, 듬성듬성한 물건(희소)은 품목 목록이 공간 낭비가 없다.

Ⅴ. 기대효과 및 결론

그래프 표현 방식의 선택은 이후 모든 그래프 알고리즘의 시간·공간 복잡도에 직접적인 영향을 미친다. 희소 그래프에서 인접 행렬을 사용하면 O(V²) 공간 낭비와 O(V) 이웃 순회 비효율이 동시에 발생하여 알고리즘 성능을 수십 배 떨어뜨린다.

핵심 결론: 그래프 알고리즘 설계의 첫 단계는 항상 "이 그래프는 희소한가, 밀집한가?"를 묻는 것이다.

📢 섹션 요약 비유: 그래프 표현 방식은 데이터베이스 스키마 설계와 같다. 잘못된 선택은 코드 한 줄 수정 없이 성능을 몇 십 배 떨어뜨린다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[:---]
    │
    ▼
[DFS (Depth-First Search)]
    │
    ▼
[BFS (Breadth-First Search)]
    │
    ▼
[플로이드-워샬]
    │
    ▼
[크루스칼 (Kruskal)]
    │
    ▼
[다익스트라 (Dijkstra)]
    │
    ▼
[희소 행렬 (Sparse Matrix)]

이 흐름도는 :---에서 출발해 다익스트라 (Dijkstra)까지 이어지며, 중간 단계가 기초 개념을 실무 구조로 발전시키는 과정을 보여준다.

👶 어린이를 위한 3줄 비유 설명

1. 🗺️ 그래프는 도시들(정점)과 도로들(간선)로 이루어진 지도인데, 이 지도를 컴퓨터에 기록하는 방법이 두 가지다.
2. 📊 인접 행렬은 모든 도시 쌍에 대해 "도로 있음/없음"을 큰 표에 적는 방식이고, 인접 리스트는 각 도시의 메모장에 연결된 도시만 적는 방식이다.
3. 🏙️ 도시가 많고 도로가 적으면 메모장 방식이 훨씬 효율적이고, 도로가 거의 모두 연결되어 있으면 표 방식이 더 빠르다.