icon

안동민 개발노트

7장: 그래프 기초

그래프 모델링과 표현 방식

그래프 문제는 BFS/DFS 코드보다 입력을 어떻게 담을지 우선 정해야 합니다. 같은 간선 데이터라도 인접 리스트와 인접 행렬 중 무엇을 고르느냐에 따라 메모리 사용량과 실행 시간이 크게 달라집니다.

탐색부터 바로 코딩하면 중간에 모델이 맞지 않아 다시 짜는 일이 자주 생깁니다. 여기서는 탐색 전에 정할 항목(방향성, 가중치, 다중 간선)을 우선 고정하는 흐름으로 설명합니다. 모델을 정확히 만들면 이후 알고리즘 선택이 훨씬 안정적입니다.

그래프 모델링 의사결정 맵: 인접 리스트와 인접 행렬 선택 기준

핵심 개념: 그래프 모델링과 표현

그래프 표현은 알고리즘보다 우선 결정해야 하는 기초 설계입니다. 지금 문제를 보고 정점 수와 간선 수를 우선 적은 뒤 희소/밀집 여부를 판단해 보세요.

그래프 모델링은 문제 대상을 정점과 간선으로 바꾸는 추상화 작업입니다. 정확히는 객체를 정점 집합 V, 관계를 간선 집합 E로 사상해 계산 가능한 형태로 만드는 과정입니다. 도시를 정점, 도로를 간선으로 바꾸면 길 찾기 문제를 그래프 알고리즘으로 바로 연결할 수 있습니다.

인접 리스트는 각 정점의 이웃만 저장하는 표현입니다. 필요한 간선만 저장하므로 공간 효율이 좋고 순회 비용을 O(V+E)로 처리할 수 있습니다. 1:[2,3], 2:[4]처럼 연결된 정점만 적기 때문에 희소 그래프에서 특히 유리합니다.

인접 행렬은 정점 쌍의 연결 여부를 V x V 표로 저장하는 방식입니다. matrix[u][v] 조회 한 번으로 연결을 확인할 수 있어 존재 질의가 많을 때 강점이 있습니다. 대신 정점 수가 크면 공간 사용량이 급격히 커지므로 밀집 그래프나 잦은 연결 질의에서만 신중히 선택해야 합니다.

그래프 모델링이 실무에서 중요한 이유

탐색 복잡도 O(V+E)를 외워도 표현 선택이 틀리면 실제 성능은 나빠집니다.
예를 들어 정점이 100,000개인데 행렬을 선택하면 메모리만으로도 문제가 됩니다.

또한 방향성/가중치/다중 간선 여부를 모델 단계에서 고정하지 않으면,
이후 BFS/DFS/최단 경로 코드 전체가 흔들립니다.

모델링 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

같은 간선을 두 표현으로 만들어 차이를 확인합니다.

  • 간선: (0,1), (1,2), (2,3)
  • 정점 수: 4
  1. 인접 리스트는 실제 간선만 저장해 공간이 작습니다.
  2. 인접 행렬은 4x4 공간을 항상 사용하지만 간선 존재 조회가 즉시 가능합니다.
  3. 질의 패턴(간선 조회 잦음 vs 이웃 순회 잦음)에 따라 선택이 바뀝니다.

그래프 모델: 인접 리스트 구성

문제 의도: 정점 수와 간선 목록으로 인접 리스트를 만드는 가장 기본 패턴을 익힙니다.
입력 예시: n=5, edges=[(0,1),(1,2),(2,3)]
출력 예시: 정점별 이웃 리스트

main.cpp
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int>> buildAdjList(int n, const vector<pair<int, int>>& edges, bool directed = false) {
    vector<vector<int>> graph(n);
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        if (!directed) graph[v].push_back(u);
    }
    return graph;
}

int main() {
    int n = 5;
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
    auto g = buildAdjList(n, edges, false);
    for (int u = 0; u < n; ++u) {
        cout << u << " -> ";
        for (int v : g[u]) cout << v << " ";
        cout << "\n";
    }
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> buildAdjList(int n, int[][] edges, boolean directed) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph.get(u).add(v);
            if (!directed) graph.get(v).add(u);
        }
        return graph;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
        List<List<Integer>> g = buildAdjList(n, edges, false);
        for (int u = 0; u < n; u++) {
            System.out.println(u + " -> " + g.get(u));
        }
    }
}
main.py
def build_adj_list(n, edges, directed=False):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

n = 5
edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
g = build_adj_list(n, edges, directed=False)
for u in range(n):
    print(u, "->", g[u])
main.rs
fn build_adj_list(n: usize, edges: &[(usize, usize)], directed: bool) -> Vec<Vec<usize>> {
    let mut graph = vec![Vec::<usize>::new(); n];
    for &(u, v) in edges {
        graph[u].push(v);
        if !directed {
            graph[v].push(u);
        }
    }
    graph
}

fn main() {
    let n = 5usize;
    let edges = vec![(0, 1), (1, 2), (2, 3), (3, 4)];
    let graph = build_adj_list(n, &edges, false);
    for u in 0..n {
        println!("{u} -> {:?}", graph[u]);
    }
}

그래프 모델링 결과 그래프 모델 조건 검토

인접 리스트는 실제 간선 수만큼만 저장하므로 희소 그래프에 유리합니다.
방향 그래프 여부는 간선 추가 시점에 결정합니다.
문제에서 방향성이 섞이면 입력 파싱 단계에서 분리 처리하는 것이 안전합니다.

  • 평균 공간복잡도: O(V + E)
  • 평균 시간복잡도: 그래프 생성 O(E), 정점 u의 이웃 순회 O(deg(u))

그래프 모델: 인접 행렬 구성

문제 의도: 간선 존재 조회가 빠른 인접 행렬 모델을 구성합니다.
입력 예시: n=5, edges=[(0,1),(1,2),(2,3)]
출력 예시: mat[0][1]=1, mat[0][4]=0

main.cpp
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int>> buildAdjMatrix(int n, const vector<pair<int, int>>& edges, bool directed = false) {
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        mat[u][v] = 1;
        if (!directed) mat[v][u] = 1;
    }
    return mat;
}

int main() {
    auto m = buildAdjMatrix(5, {{0, 1}, {1, 2}, {2, 3}}, false);
    cout << m[0][1] << " " << m[0][4] << "\n";
    return 0;
}
Main.java
public class Main {
    static int[][] buildAdjMatrix(int n, int[][] edges, boolean directed) {
        int[][] mat = new int[n][n];
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            mat[u][v] = 1;
            if (!directed) mat[v][u] = 1;
        }
        return mat;
    }

    public static void main(String[] args) {
        int[][] m = buildAdjMatrix(5, new int[][]{{0,1},{1,2},{2,3}}, false);
        System.out.println(m[0][1] + " " + m[0][4]);
    }
}
main.py
def build_adj_matrix(n, edges, directed=False):
    mat = [[0] * n for _ in range(n)]

    for u, v in edges:
        mat[u][v] = 1
        if not directed:
            mat[v][u] = 1

    return mat

m = build_adj_matrix(5, [(0, 1), (1, 2), (2, 3)], directed=False)
print(m[0][1], m[0][4])  # 1 0
main.rs
fn build_adj_matrix(n: usize, edges: &[(usize, usize)], directed: bool) -> Vec<Vec<i32>> {
    let mut mat = vec![vec![0; n]; n];
    for &(u, v) in edges {
        mat[u][v] = 1;
        if !directed {
            mat[v][u] = 1;
        }
    }
    mat
}

fn main() {
    let m = build_adj_matrix(5, &[(0, 1), (1, 2), (2, 3)], false);
    println!("{} {}", m[0][1], m[0][4]);
}

그래프 모델링 결과 방문 순서 추적

행렬은 간선 존재 확인이 O(1)로 빠릅니다.
다만 정점 수가 크면 O(V^2) 메모리 비용이 치명적일 수 있습니다.
밀집 그래프이거나 간선 존재 질의가 매우 많은 경우에 선택 가치가 있습니다.

  • 시간복잡도: 행렬 생성 O(V^2 + E), 간선 질의 O(1)
  • 공간복잡도: O(V^2)

그래프 모델: 가중치 그래프 모델

문제 의도: 가중치 포함 간선을 그래프 모델에 반영하는 패턴을 학습합니다.
입력 예시: edges=[(1,2,5),(1,3,2),(3,2,1)]
출력 예시: 정점별 (이웃,가중치) 목록

main.cpp
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

unordered_map<int, vector<pair<int, int>>> buildWeighted(const vector<tuple<int, int, int>>& edges, bool directed = true) {
    unordered_map<int, vector<pair<int, int>>> g;
    for (const auto& edge : edges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int w = get<2>(edge);
        g[u].push_back({v, w});
        if (!directed) g[v].push_back({u, w});
    }
    return g;
}

int main() {
    auto g = buildWeighted({{1, 2, 5}, {1, 3, 2}, {3, 2, 1}}, true);
    for (const auto& item : g[1]) {
        int v = item.first;
        int w = item.second;
        cout << "(" << v << ", " << w << ") ";
    }
    cout << "\n";
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static class Edge {
        int to, w;
        Edge(int to, int w) { this.to = to; this.w = w; }
        @Override
        public String toString() { return "(" + to + ", " + w + ")"; }
    }

    static Map<Integer, List<Edge>> buildWeighted(int[][] edges, boolean directed) {
        Map<Integer, List<Edge>> g = new HashMap<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            g.computeIfAbsent(u, k -> new ArrayList<>()).add(new Edge(v, w));
            if (!directed) g.computeIfAbsent(v, k -> new ArrayList<>()).add(new Edge(u, w));
        }
        return g;
    }

    public static void main(String[] args) {
        Map<Integer, List<Edge>> g = buildWeighted(new int[][]{{1,2,5},{1,3,2},{3,2,1}}, true);
        System.out.println(g.get(1));
    }
}
main.py
from collections import defaultdict

def build_weighted(edges, directed=True):
    g = defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))
        if not directed:
            g[v].append((u, w))
    return g

wg = build_weighted([(1, 2, 5), (1, 3, 2), (3, 2, 1)], directed=True)
print(wg[1])  # [(2, 5), (3, 2)]
main.rs
use std::collections::HashMap;

fn build_weighted(edges: &[(i32, i32, i32)], directed: bool) -> HashMap<i32, Vec<(i32, i32)>> {
    let mut g: HashMap<i32, Vec<(i32, i32)>> = HashMap::new();
    for &(u, v, w) in edges {
        g.entry(u).or_default().push((v, w));
        if !directed {
            g.entry(v).or_default().push((u, w));
        }
    }
    g
}

fn main() {
    let g = build_weighted(&[(1, 2, 5), (1, 3, 2), (3, 2, 1)], true);
    if let Some(items) = g.get(&1) {
        println!("{:?}", items);
    } else {
        println!("[]");
    }
}

그래프 모델링 결과 경로/사이클 재확인

가중치가 있는 문제는 간선 타입을 (to, weight)로 고정하면 이후 알고리즘 구현이 단순해집니다.
모델 타입이 흔들리면 Dijkstra, Bellman-Ford 같은 후속 코드에서 버그가 쉽게 생깁니다.

  • 시간복잡도: 그래프 생성 O(E)
  • 공간복잡도: O(V + E)

인접 리스트/행렬 운용 관점

표현 방식 선택 시 다음을 우선 확인합니다.

  • 정점 수와 간선 수 규모
  • 간선 존재 질의 빈도
  • 방향/무방향 여부
  • 가중치/다중 간선 필요 여부

모델링 단계에서 이 항목을 고정하면 탐색 코드 재작업을 크게 줄일 수 있습니다.

모델링 균형 지점

그래프 표현의 대표적인 균형점입니다.

  • 인접 리스트: 메모리 효율 좋음 / 존재 질의는 상대적으로 느림
  • 인접 행렬: 존재 질의 빠름 / 메모리 비용 큼
  • 리스트: 구현 유연 / 중복 간선 관리 필요
  • 행렬: 구현 단순 / 희소 그래프에 비효율

문제의 주요 연산이 무엇인지가 최종 선택을 결정합니다.

그래프 모델: 간선 존재 질의 비교

문제 의도: 리스트/행렬 표현에서 간선 존재 질의 비용 차이를 비교합니다.
입력 예시: 동일 간선 집합으로 두 표현 구성 후 has_edge(u,v) 실행
출력 예시: 질의 결과와 방식별 특성 비교

main.cpp
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

unordered_map<int, vector<int>> buildAdjList(const vector<pair<int, int>>& edges, bool directed) {
    unordered_map<int, vector<int>> g;
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        g[u].push_back(v);
        if (!directed) g[v].push_back(u);
    }
    return g;
}

vector<vector<int>> buildAdjMatrix(int n, const vector<pair<int, int>>& edges, bool directed) {
    vector<vector<int>> mat(n, vector<int>(n, 0));
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        mat[u][v] = 1;
        if (!directed) mat[v][u] = 1;
    }
    return mat;
}

bool hasEdgeList(const unordered_map<int, vector<int>>& g, int u, int v) {
    auto it = g.find(u);
    if (it == g.end()) return false;
    for (int x : it->second) if (x == v) return true;
    return false;
}

bool hasEdgeMatrix(const vector<vector<int>>& mat, int u, int v) {
    return mat[u][v] == 1;
}

int main() {
    auto elist = buildAdjList({{1, 2}, {1, 3}, {2, 4}}, true);
    auto emat = buildAdjMatrix(5, {{1, 2}, {1, 3}, {2, 4}}, true);
    cout << hasEdgeList(elist, 1, 3) << "\n";
    cout << hasEdgeMatrix(emat, 1, 3) << "\n";
    cout << hasEdgeList(elist, 3, 1) << "\n";
    cout << hasEdgeMatrix(emat, 3, 1) << "\n";
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static Map<Integer, List<Integer>> buildAdjList(int[][] edges, boolean directed) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            g.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            if (!directed) g.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }
        return g;
    }

    static int[][] buildAdjMatrix(int n, int[][] edges, boolean directed) {
        int[][] mat = new int[n][n];
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            mat[u][v] = 1;
            if (!directed) mat[v][u] = 1;
        }
        return mat;
    }

    static boolean hasEdgeList(Map<Integer, List<Integer>> graph, int u, int v) {
        return graph.getOrDefault(u, List.of()).contains(v);
    }

    static boolean hasEdgeMatrix(int[][] mat, int u, int v) {
        return mat[u][v] == 1;
    }

    public static void main(String[] args) {
        int[][] edges = {{1,2},{1,3},{2,4}};
        var elist = buildAdjList(edges, true);
        var emat = buildAdjMatrix(5, edges, true);
        System.out.println(hasEdgeList(elist, 1, 3));
        System.out.println(hasEdgeMatrix(emat, 1, 3));
        System.out.println(hasEdgeList(elist, 3, 1));
        System.out.println(hasEdgeMatrix(emat, 3, 1));
    }
}
main.py
def has_edge_list(graph, u, v):
    return v in graph.get(u, [])

def has_edge_matrix(mat, u, v):
    return mat[u][v] == 1

def build_adj_list(edges, directed=False):
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        if not directed:
            graph.setdefault(v, []).append(u)
    return graph

def build_adj_matrix(n, edges, directed=False):
    mat = [[0] * n for _ in range(n)]
    for u, v in edges:
        mat[u][v] = 1
        if not directed:
            mat[v][u] = 1
    return mat

elist = build_adj_list([(1, 2), (1, 3), (2, 4)], directed=True)
emat = build_adj_matrix(5, [(1, 2), (1, 3), (2, 4)], directed=True)

print(has_edge_list(elist, 1, 3))   # True
print(has_edge_matrix(emat, 1, 3))  # True
print(has_edge_list(elist, 3, 1))   # False
print(has_edge_matrix(emat, 3, 1))  # False
main.rs
use std::collections::HashMap;

fn build_adj_list(edges: &[(usize, usize)], directed: bool) -> HashMap<usize, Vec<usize>> {
    let mut graph: HashMap<usize, Vec<usize>> = HashMap::new();
    for &(u, v) in edges {
        graph.entry(u).or_default().push(v);
        if !directed {
            graph.entry(v).or_default().push(u);
        }
    }
    graph
}

fn build_adj_matrix(n: usize, edges: &[(usize, usize)], directed: bool) -> Vec<Vec<i32>> {
    let mut mat = vec![vec![0; n]; n];
    for &(u, v) in edges {
        mat[u][v] = 1;
        if !directed {
            mat[v][u] = 1;
        }
    }
    mat
}

fn has_edge_list(graph: &HashMap<usize, Vec<usize>>, u: usize, v: usize) -> bool {
    if let Some(xs) = graph.get(&u) {
        for &item in xs {
            if item == v {
                return true;
            }
        }
    }
    false
}

fn has_edge_matrix(mat: &[Vec<i32>], u: usize, v: usize) -> bool {
    mat[u][v] == 1
}

fn main() {
    let edges = vec![(1, 2), (1, 3), (2, 4)];
    let elist = build_adj_list(&edges, true);
    let emat = build_adj_matrix(5, &edges, true);
    println!("{}", has_edge_list(&elist, 1, 3));
    println!("{}", has_edge_matrix(&emat, 1, 3));
    println!("{}", has_edge_list(&elist, 3, 1));
    println!("{}", has_edge_matrix(&emat, 3, 1));
}

추가 케이스 그래프 모델링 결과 해석

행렬은 간선 존재 확인이 즉시 O(1)입니다.
리스트는 해당 정점 차수만큼 확인해야 하므로 O(deg(u))입니다.
질의 빈도가 높고 그래프가 밀집된 경우 행렬 선택의 분기 이유가 됩니다.

  • 시간복잡도: 리스트 질의 O(deg(u)), 행렬 질의 O(1) (1회 질의 기준)
  • 공간복잡도: 리스트 O(V + E), 행렬 O(V^2)

모델링 체크리스트

그래프 코드를 작성하기 전에 아래 항목을 우선 고정합니다.

  • 정점 ID 범위와 인덱스 기준
  • 방향성 여부와 자기 루프 허용 여부
  • 중복 간선 정책(허용/병합)
  • 가중치 타입과 범위
  • 파싱 실패 입력 처리 정책

이 체크리스트를 초기 문서에 포함하면 구현 단계의 해석 차이를 줄일 수 있습니다.

그래프 모델 운영 관찰 지표

모델링 품질을 운영에서 확인하려면 다음 지표를 함께 수집합니다.

  • 정점 수/간선 수 추이
  • 평균 차수와 최대 차수
  • 고립 노드 비율
  • 파싱 실패 입력 비율

지표가 없으면 모델 자체 문제를 알고리즘 문제로 오판하기 쉽습니다. 초기 단계부터 지표를 수집하면 데이터 성장에 따른 구조 변경 시점을 더 정확히 잡을 수 있습니다. 이 판단이 늦어질수록 전체 그래프 처리 파이프라인의 수정 비용이 커집니다.

그래프 표현 로그 실수 포인트

그래프 모델링에서 자주 틀리는 부분입니다.

  • 방향 그래프를 무방향으로 잘못 구성
  • 1-based/0-based 인덱스 혼동
  • 고립 노드 누락
  • 다중 간선/자기 루프 정책 미정의

모델링 테스트는 간단한 그래프뿐 아니라 고립 노드/사이클 그래프를 함께 포함해야 합니다.

그래프 표현 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 선택 관점을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

표현공간간선 존재 확인인접 순회
인접 리스트O(V+E)O(deg(v))O(deg(v))
인접 행렬O(V^2)O(1)O(V)

복잡도 표만 보지 말고 실제 입력 밀도를 함께 고려해야 합니다.

제출 직전 그래프 모델 체크

  • 모델 생성 함수와 탐색 함수의 입력 타입 계약을 문서화해야 합니다.
  • 대형 그래프에서는 파싱 비용도 전체 성능에 큰 영향을 줍니다.
  • 디버깅 시 정점 수/간선 수/고립 노드 수를 우선 로그로 확인하는 습관이 좋습니다.
  • 그래프 방향성이 문제마다 달라질 수 있으므로 기본값 사용을 최소화합니다.

그래프 모델 구현 점검 목록

  • 방향성/가중치/다중 간선 정책을 모델 단계에서 고정했는가
  • 입력 밀도에 따라 리스트/행렬을 합리적으로 선택했는가
  • 0-based/1-based 인덱스를 일관되게 처리했는가
  • 고립 노드 포함 케이스를 테스트에 넣었는가

그래프 표현 선택 정리

그래프 알고리즘은 모델링이 절반입니다.
입력 표현을 정확히 고정하면 탐색과 최적화 단계가 훨씬 안정적으로 진행됩니다.

우선순위 큐 설계와 안정성

이전 페이지

BFS와 DFS 템플릿

다음 페이지

목차

핵심 개념: 그래프 모델링과 표현
그래프 모델링이 실무에서 중요한 이유
모델링 오답 재현으로 검증하기
그래프 모델: 인접 리스트 구성
그래프 모델링 결과 그래프 모델 조건 검토
그래프 모델: 인접 행렬 구성
그래프 모델링 결과 방문 순서 추적
그래프 모델: 가중치 그래프 모델
그래프 모델링 결과 경로/사이클 재확인
인접 리스트/행렬 운용 관점
모델링 균형 지점
그래프 모델: 간선 존재 질의 비교
추가 케이스 그래프 모델링 결과 해석
모델링 체크리스트
그래프 모델 운영 관찰 지표
그래프 표현 로그 실수 포인트
그래프 표현 비용 모델 정리
제출 직전 그래프 모델 체크
그래프 모델 구현 점검 목록
그래프 표현 선택 정리