pkglog
EN

그래프 자료구조: 인접 리스트와 인접 행렬, 그래프 탐색 기초

작성 · · 23분 읽기 · 수정 중급 튜토리얼

이 글의 핵심

그래프 문제에서 틀리는 원인은 알고리즘보다 방문 체크 누락, 방향·무방향 혼동, 1-indexed 노드 번호, 큰 N에서 인접 행렬로 인한 메모리 초과 같은 구현 실수인 경우가 많습니다. 표현 방식 선택 가이드와 함께 이런 문제를 트러블슈팅 사례로 정리했습니다.

시리즈 안내

#05 | 📋 전체 목차 | 이전: #04 트리 · 다음: #06 기본 정렬

들어가며

그래프는 노드(정점)와 간선으로 이루어진 자료구조입니다. 트리보다 일반적인 구조로, 사이클을 허용하며 네트워크, 지도, 소셜 관계 등 실생활의 복잡한 연결 관계를 표현할 수 있습니다.

이 글을 읽으면

  • 그래프의 기본 용어와 종류를 이해합니다
  • 인접 리스트와 인접 행렬의 차이를 구분합니다
  • BFS와 DFS로 그래프를 탐색하는 코드를 작성합니다
  • 실무에서 그래프를 활용하는 사례를 학습합니다

그래프 기본

용어 정리

    1 --- 2
    |     |
    3 --- 4
- 정점(Vertex/Node): 1, 2, 3, 4
- 간선(Edge): 1-2, 1-3, 2-4, 3-4
- 차수(Degree): 정점에 연결된 간선 수
  - 1의 차수 = 2 (1-2, 1-3)
  - 2의 차수 = 2 (1-2, 2-4)
- 경로(Path): 1 → 2 → 4
- 사이클(Cycle): 1 → 2 → 4 → 3 → 1

그래프 종류

1) 방향 그래프 (Directed Graph)

1 → 2
↓   ↓
3 → 4
- 간선에 방향 있음
- A → B는 가능, B → A는 불가능
- 예: 웹 페이지 링크, 작업 의존성

2) 무방향 그래프 (Undirected Graph)

1 - 2
|   |
3 - 4
- 간선에 방향 없음
- A - B는 양방향 가능
- 예: 친구 관계, 도로망

3) 가중치 그래프 (Weighted Graph)

    5
1 --- 2
|  3  |
3 --- 4
    2
- 간선에 가중치(비용) 있음
- 예: 거리, 시간, 비용

4) 순환 그래프 vs 비순환 그래프

순환 (Cyclic):
1 → 2
↑   ↓
3 ← 4
비순환 (Acyclic):
1 → 2
↓   ↓
3 → 4

그래프 표현

인접 리스트 (Adjacency List)

정의: 각 정점마다 연결된 이웃 정점들의 리스트를 저장 장점:

  • 공간 효율: O(V + E)

  • 희소 그래프에 적합

  • 이웃 순회 빠름 단점:

  • 간선 존재 확인 느림: O(차수), 최악 O(V)

“간선 (u, v)가 있는가?”를 확인하려면 u의 이웃 리스트를 훑어야 하므로 비용은 u의 차수에 비례합니다. 차수가 작은 희소 그래프에서는 사실상 상수에 가깝고, 이웃을 리스트 대신 set(C++이면 unordered_set)으로 저장하면 평균 O(1)로 바꿀 수 있습니다. 대신 set은 원소마다 해시 테이블 오버헤드가 붙어 메모리를 몇 배 더 쓰고, 순회 순서가 입력 순서와 달라져 “작은 번호부터 방문” 같은 문제 조건을 맞추려면 따로 정렬해야 합니다. 코딩 테스트에서는 대부분 리스트로 충분하고, 간선 확인이 반복되는 알고리즘(삼각형 개수 세기 등)에서만 set을 고려합니다.

Python 구현

# 무방향 그래프
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
# 방향 그래프
directed_graph = {
    1: [2, 3],
    2: [4],
    3: [4],
    4: []
}
# 가중치 그래프
weighted_graph = {
    1: [(2, 5), (3, 3)],  # (노드, 가중치)
    2: [(1, 5), (4, 2)],
    3: [(1, 3), (4, 2)],
    4: [(2, 2), (3, 2)]
}
# 간선 리스트에서 인접 리스트 생성
def build_graph(n, edges, directed=False):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        if not directed:
            graph[b].append(a)
    return graph
# 사용
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
graph = build_graph(4, edges)
print(graph)
# {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}

C++ 구현

#include <vector>
#include <iostream>
using namespace std;
// 무방향 그래프
vector<vector<int>> buildGraph(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> graph(n);
    
    for (const auto& [a, b] : edges) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    return graph;
}
// 가중치 그래프
vector<vector<pair<int, int>>> buildWeightedGraph(
    int n, 
    const vector<tuple<int, int, int>>& edges
) {
    vector<vector<pair<int, int>>> graph(n);
    
    for (const auto& [a, b, weight] : edges) {
        graph[a].push_back({b, weight});
        graph[b].push_back({a, weight});
    }
    
    return graph;
}
int main() {
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
    auto graph = buildGraph(4, edges);
    
    for (int i = 0; i < graph.size(); ++i) {
        cout << i << ": ";
        for (int neighbor : graph[i]) {
            cout << neighbor << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

C++ 구현에서 정점 번호를 vector의 인덱스로 쓰는 방식은 정점이 0부터 n-1까지의 정수일 때만 가능합니다. 정점이 문자열(도시 이름, 사용자 ID)이거나 번호가 듬성듬성하면 먼저 unordered_map<string, int>로 0..n-1의 번호를 붙이는 “좌표 압축”을 하거나, Python처럼 해시맵 기반 인접 리스트를 씁니다. 번호를 붙여 두면 방문 배열도 vector<bool>이나 vector<char>로 만들 수 있어 해시 조회보다 훨씬 빠릅니다.

인접 행렬 (Adjacency Matrix)

정의: V×V 2차원 배열에서 matrix[i][j]가 간선 존재 여부 또는 가중치 장점:

  • 간선 확인 빠름: O(1)

  • 구현 간단 단점:

  • 공간 비효율: O(V²)

  • 밀집 그래프에만 적합

Python 구현

# 무방향 그래프 (4개 정점)
graph = [
    [0, 1, 1, 0],  # 0번 정점
    [1, 0, 0, 1],  # 1번 정점
    [1, 0, 0, 1],  # 2번 정점
    [0, 1, 1, 0]   # 3번 정점
]
# 가중치 그래프 (0은 연결 없음)
weighted_graph = [
    [0, 5, 3, 0],
    [5, 0, 0, 2],
    [3, 0, 0, 2],
    [0, 2, 2, 0]
]
# 간선 확인
if graph[0][1] == 1:
    print("0-1 연결됨")
# 간선 리스트에서 인접 행렬 생성
def build_matrix(n, edges, directed=False):
    matrix = [[0] * n for _ in range(n)]
    for a, b in edges:
        matrix[a][b] = 1
        if not directed:
            matrix[b][a] = 1
    return matrix
# 사용
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
matrix = build_matrix(4, edges)
print(matrix)
# [[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0]]

비교표

특징인접 리스트인접 행렬
공간O(V+E)O(V²)
간선 확인O(V)O(1)
전체 순회O(V+E)O(V²)
구현복잡간단
적합희소 그래프 (E << V²)밀집 그래프 (E ≈ V²)
예시소셜 네트워크완전 그래프

실제 선택은 표보다 V의 크기로 먼저 갈립니다. 인접 행렬은 V = 10,000이면 원소가 1억 개라 C++ bool 배열로도 약 100MB, Python 리스트로는 수 GB가 되어 거의 모든 코딩 테스트의 메모리 제한을 넘깁니다. 반대로 V가 수백 이하이고 플로이드-워셜처럼 모든 쌍의 거리를 다루는 알고리즘이라면 행렬이 코드도 간단하고 캐시 효율도 좋습니다. 백준 기준으로 “V ≤ 1,000 정도면 행렬도 가능, 그 이상은 리스트”를 출발점으로 삼으면 대부분 맞습니다.

그래프 탐색

BFS (너비 우선 탐색)

원리: 시작 정점에서 가까운 정점부터 방문 구현 (Python):

from collections import deque
def bfs(graph, start):
    """
    BFS 탐색
    - 큐 사용
    - 최단 경로 보장 (무가중치)
    """
    visited = set([start])
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result
# 테스트
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
print(bfs(graph, 1))  # [1, 2, 3, 4]

구현 (C++):

#include <vector>
#include <queue>
#include <unordered_set>
#include <iostream>
using namespace std;
vector<int> bfs(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;
    vector<int> result;
    
    visited.insert(start);
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
    
    return result;
}
int main() {
    vector<vector<int>> graph = {
        {1, 2},  // 0번 정점
        {0, 3},  // 1번 정점
        {0, 3},  // 2번 정점
        {1, 2}   // 3번 정점
    };
    
    auto result = bfs(graph, 0);
    for (int node : result) {
        cout << node << " ";
    }
    // 출력: 0 1 2 3
    
    return 0;
}

시간 복잡도: O(V + E) 공간 복잡도: O(V)

BFS에서 방문 표시를 큐에 넣을 때 하는 것이 중요합니다. 꺼낼 때 표시하면 같은 정점이 아직 처리되기 전에 여러 이웃에게서 중복으로 큐에 들어가, 밀집 그래프에서는 큐 크기가 O(E)까지 커지고 시간도 늘어납니다. 최단 거리 문제에서는 더 심각해서, 꺼낼 때 표시하면 늦게 들어온 더 긴 경로의 거리가 덮어써질 수 있습니다. 파이썬에서 queue = [start]와 queue.pop(0)으로 BFS를 짜는 것도 흔한 실수인데, list.pop(0)은 뒤 원소를 전부 한 칸씩 당기는 O(n) 연산이라 큰 그래프에서 시간 초과가 납니다. 위 코드처럼 collections.deque의 popleft()를 써야 O(1)입니다.

DFS (깊이 우선 탐색)

원리: 한 경로를 끝까지 탐색 후 백트래킹 구현 (Python - 재귀):

def dfs_recursive(graph, node, visited, result):
    """
    DFS 탐색 (재귀)
    - 스택 사용 (암시적: 호출 스택)
    - 각 정점을 한 번씩 방문 (모든 "경로"를 나열하는 것은 아님)
    """
    visited.add(node)
    result.append(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
# 사용
graph = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}
visited = set()
result = []
dfs_recursive(graph, 1, visited, result)
print(result)  # [1, 2, 4, 3]

재귀 DFS는 코드가 짧지만 파이썬에서는 재귀 깊이 제한(기본 1000) 에 바로 걸립니다. 정점이 일렬로 이어진 그래프(경로 그래프)나 큰 그리드에서 DFS를 돌리면 RecursionError: maximum recursion depth exceeded가 나고, sys.setrecursionlimit(10**6)으로 한도를 올려도 실제 C 스택이 부족하면 인터프리터가 세그멘테이션 폴트로 죽을 수 있습니다. 저도 백준에서 정점 10만 개짜리 트리 문제를 재귀 DFS로 풀다가 로컬에서는 통과하고 채점 서버에서 런타임 에러가 난 적이 있는데, 결국 아래의 반복 DFS로 바꿔서 해결했습니다. C++도 기본 스택(보통 1~8MB)을 넘기면 스택 오버플로가 나므로, 깊이가 10만 이상일 수 있으면 반복 버전을 쓰는 편이 안전합니다.

구현 (Python - 반복):

def dfs_iterative(graph, start):
    """
    DFS 탐색 (반복)
    - 명시적 스택 사용
    """
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result
# 테스트
print(dfs_iterative(graph, 1))  # [1, 2, 4, 3]

반복 DFS는 BFS와 달리 꺼낼 때(pop) 방문 표시를 합니다. 넣을 때 표시하면 “먼저 발견한 순서”가 고정되어 재귀 DFS와 방문 순서가 달라지기 때문입니다. 그 대신 같은 정점이 스택에 여러 번 들어갈 수 있어 스택 크기가 최악 O(E)가 되고, if node not in visited 검사로 중복을 걸러 냅니다. 이웃을 reversed로 넣는 이유는 스택이 나중에 넣은 것을 먼저 꺼내므로, 역순으로 넣어야 재귀 버전과 같은 “작은 번호부터” 순서가 나오기 때문입니다. 방문 순서가 채점에 영향을 주는 문제(백준 1260 등)에서는 이 차이 때문에 정답과 출력이 달라집니다. 구현 (C++):

#include <vector>
#include <stack>
#include <unordered_set>
#include <iostream>
using namespace std;
vector<int> dfs(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    stack<int> st;
    vector<int> result;
    
    st.push(start);
    
    while (!st.empty()) {
        int node = st.top();
        st.pop();
        
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            result.push_back(node);
            
            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (visited.find(*it) == visited.end()) {
                    st.push(*it);
                }
            }
        }
    }
    
    return result;
}
int main() {
    vector<vector<int>> graph = {
        {1, 2},  // 0번 정점
        {0, 3},  // 1번 정점
        {0, 3},  // 2번 정점
        {1, 2}   // 3번 정점
    };
    
    auto result = dfs(graph, 0);
    for (int node : result) {
        cout << node << " ";
    }
    // 출력: 0 1 3 2
    
    return 0;
}

시간 복잡도: O(V + E) 공간 복잡도: O(V)

C++ 예제의 unordered_set<int> visited는 정점 번호가 0..n-1이면 vector<bool> visited(n)으로 바꾸는 것이 좋습니다. 해시 계산과 버킷 조회가 없어 수 배 빠르고 메모리도 적게 씁니다. 해시 기반 방문 집합은 정점이 문자열이거나 좌표 쌍처럼 인덱스로 쓸 수 없을 때를 위한 선택입니다.

고급 활용

연결 요소 개수 (Connected Components)

문제: 무방향 그래프에서 연결된 컴포넌트 개수 찾기

Python 구현

def count_components(n, edges):
    """
    연결 요소 개수
    - Union-Find 또는 DFS 사용
    """
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = set()
    count = 0
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
    
    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    
    return count
# 테스트
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(count_components(n, edges))  # 2
# 컴포넌트 1: {0, 1, 2}
# 컴포넌트 2: {3, 4}

사이클 감지

방향 그래프:

def has_cycle_directed(graph):
    """
    방향 그래프 사이클 감지
    - 재귀 스택 추적
    """
    visited = set()
    rec_stack = set()
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    
    return False
# 테스트
graph = {1: [2], 2: [3], 3: [1]}  # 사이클: 1→2→3→1
print(has_cycle_directed(graph))  # True

방향 그래프에서 visited만으로는 사이클을 판별할 수 없는 이유는, “이미 방문한 정점”을 다시 만나는 경우가 두 가지이기 때문입니다. 현재 DFS 경로 위에 있는 정점(조상)을 다시 만나면 사이클이지만, 다른 가지에서 이미 탐색을 끝낸 정점을 만나는 것은 1→2, 1→3, 2→4, 3→4 같은 다이아몬드 구조일 뿐 사이클이 아닙니다. rec_stack이 “지금 경로 위에 있는 정점”을 추적해 두 경우를 구분하며, 흔히 흰색(미방문)·회색(경로 위)·검은색(완료) 세 가지 색으로 설명하는 것과 같은 방법입니다. 이 코드는 for node in graph로 딕셔너리 키만 순회하므로, 나가는 간선이 없는 정점이 키로 등록되어 있지 않으면 graph[neighbor]에서 KeyError가 납니다. 입력을 만들 때 모든 정점을 빈 리스트로 먼저 등록해 두세요. 무방향 그래프:

def has_cycle_undirected(graph):
    """
    무방향 그래프 사이클 감지
    - 부모 노드 추적
    """
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    
    return False
# 테스트
graph = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}
print(has_cycle_undirected(graph))  # True (1-2-4-3-1)

무방향 그래프는 간선을 양쪽에 저장하므로 1→2로 내려간 뒤 2의 이웃에서 1을 다시 보게 되는데, 이것은 방금 타고 온 간선이지 사이클이 아닙니다. 그래서 부모를 제외하고 이미 방문한 정점을 만났을 때만 사이클로 판단합니다. 같은 두 정점 사이에 간선이 두 개 있는 다중 간선이 입력에 있으면 그 자체가 길이 2인 사이클인데, 부모 정점 번호만으로 비교하는 이 코드는 이를 놓칩니다. 그런 입력이 가능하다면 부모 “정점” 대신 부모 “간선 번호”를 기억하거나, 간선을 하나씩 추가하며 Union-Find로 같은 집합에 속한 두 정점을 잇는 순간을 사이클로 판정하는 방법이 더 견고합니다.

위상 정렬 (Topological Sort)

문제: 방향 비순환 그래프(DAG)에서 선후 관계 정렬

Python 구현 (Kahn’s Algorithm)

from collections import deque, defaultdict
def topological_sort(n, edges):
    """
    위상 정렬 (Kahn's Algorithm)
    - 진입 차수 0인 노드부터 처리
    """
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for a, b in edges:
        graph[a].append(b)
        in_degree[b] += 1
    
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != n:
        return []
    
    return result
# 테스트 (과목 선수 조건)
n = 4
edges = [[1, 0], [2, 0], [3, 1], [3, 2]]
# 3 → 1 → 0
#   ↘ 2 ↗
print(topological_sort(n, edges))  # [3, 1, 2, 0] 또는 [3, 2, 1, 0]

Kahn 알고리즘은 결과 길이가 n보다 짧으면 사이클이 있다는 뜻이라, 정렬과 사이클 검사를 한 번에 해 줍니다. 사이클에 속한 정점들은 서로의 진입 차수를 영원히 0으로 만들지 못해 큐에 들어가지 못하기 때문입니다. 실제 문제에 적용할 때 가장 많이 틀리는 곳은 간선 방향의 해석입니다. 이 코드는 [a, b]를 a→b(a가 먼저)로 읽지만, LeetCode 207/210의 prerequisites[i] = [a, b]는 “a를 들으려면 b를 먼저”라서 b→a로 넣어야 합니다. 방향을 반대로 넣으면 결과가 정확히 뒤집힌 순서가 나와 예제 하나로는 틀린 줄 모르고 넘어가기 쉽습니다. 여러 정답 중 사전순으로 가장 앞선 순서를 요구하는 문제라면 deque 대신 heapq 우선순위 큐를 쓰면 됩니다. 시간 복잡도: O(V + E)

실무 사례

사례 1: 소셜 네트워크 - 친구 추천

시나리오: 친구의 친구 중 아직 친구가 아닌 사람 추천

Python 구현

from collections import defaultdict
class SocialNetwork:
    def __init__(self):
        self.graph = defaultdict(set)
    
    def add_friendship(self, user1, user2):
        self.graph[user1].add(user2)
        self.graph[user2].add(user1)
    
    def recommend_friends(self, user, limit=5):
        """
        친구의 친구 추천
        - 2-hop 거리의 사용자
        - 공통 친구 수로 정렬
        """
        friends = self.graph[user]
        candidates = defaultdict(int)
        
        for friend in friends:
            for friend_of_friend in self.graph[friend]:
                if friend_of_friend != user and friend_of_friend not in friends:
                    candidates[friend_of_friend] += 1
        
        sorted_candidates = sorted(
            candidates.items(), 
            key=lambda x: x[1], 
            reverse=True
        )
        
        return [user_id for user_id, _ in sorted_candidates[:limit]]
# 사용
network = SocialNetwork()
network.add_friendship('Alice', 'Bob')
network.add_friendship('Bob', 'Charlie')
network.add_friendship('Bob', 'David')
network.add_friendship('Charlie', 'Eve')
print(network.recommend_friends('Alice'))
# ['Charlie', 'David'] (Bob을 통한 연결)

defaultdict(set)은 편하지만, 존재하지 않는 사용자로 recommend_friends('Zoe')를 호출하기만 해도 self.graph['Zoe']가 빈 집합으로 새로 생성됩니다. 조회 함수가 자료구조를 조용히 키우는 셈이라, 오래 도는 서비스에서는 self.graph.get(user, set())처럼 읽기 전용 접근을 쓰는 것이 좋습니다. 또 친구 수가 수천 명인 사용자가 많은 실제 소셜 그래프에서 2-hop 후보는 친구 수의 제곱에 비례해 폭증하므로, 서비스에서는 친구 목록을 샘플링하거나 오프라인 배치로 후보를 미리 계산해 두는 방식이 일반적입니다.

사례 2: 작업 스케줄링 - 의존성 해결

시나리오: 빌드 시스템에서 작업 순서 결정

Python 구현

from collections import defaultdict, deque
class TaskScheduler:
    def __init__(self):
        self.graph = defaultdict(list)
        self.in_degree = defaultdict(int)
    
    def add_dependency(self, task, depends_on):
        """
        task는 depends_on 이후에 실행
        """
        self.graph[depends_on].append(task)
        self.in_degree[task] += 1
        if depends_on not in self.in_degree:
            self.in_degree[depends_on] = 0
    
    def get_execution_order(self):
        """
        위상 정렬로 실행 순서 반환
        """
        queue = deque([task for task, degree in self.in_degree.items() if degree == 0])
        result = []
        
        while queue:
            task = queue.popleft()
            result.append(task)
            
            for dependent in self.graph[task]:
                self.in_degree[dependent] -= 1
                if self.in_degree[dependent] == 0:
                    queue.append(dependent)
        
        if len(result) != len(self.in_degree):
            raise ValueError("순환 의존성 감지!")
        
        return result
# 사용
scheduler = TaskScheduler()
scheduler.add_dependency('compile', 'download')
scheduler.add_dependency('test', 'compile')
scheduler.add_dependency('deploy', 'test')
scheduler.add_dependency('compile', 'generate')
print(scheduler.get_execution_order())
# ['download', 'generate', 'compile', 'test', 'deploy']

사례 3: 미로 탐색 - 최단 경로

시나리오: 2D 그리드에서 시작점에서 도착점까지 최단 경로

Python 구현

from collections import deque
def shortest_path_grid(grid, start, end):
    """
    2D 그리드 최단 경로
    - BFS 사용
    - 0: 통행 가능, 1: 벽
    """
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    queue = deque([(start[0], start[1], 0)])
    visited = {start}
    
    while queue:
        r, c, dist = queue.popleft()
        
        if (r, c) == end:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < rows and 0 <= nc < cols and 
                grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    
    return -1
# 테스트
grid = [
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0]
]
start = (0, 0)
end = (3, 3)
print(shortest_path_grid(grid, start, end))  # 6

그리드는 칸이 정점, 상하좌우 인접이 간선인 암묵적 그래프라서 인접 리스트를 따로 만들지 않고 directions로 이웃을 즉석에서 계산합니다. 간선 가중치가 모두 1이므로 BFS가 처음 도착점을 꺼내는 순간의 dist가 최단 거리이고, 가중치가 서로 다르면(진흙 칸은 비용 3 등) BFS 대신 다익스트라가 필요합니다. 가중치가 0과 1뿐이라면 0 간선은 덱 앞에, 1 간선은 뒤에 넣는 0-1 BFS로 다익스트라보다 빠르게 풀 수 있습니다. 좌표를 튜플로 set에 넣는 대신 visited = [[False] * cols for _ in range(rows)] 2차원 배열을 쓰면 큰 그리드에서 상당히 빨라집니다.

트러블슈팅

문제 1: 무한 루프 (방문 체크 누락)

증상:

def dfs_wrong(graph, node):
    print(node)
    for neighbor in graph[node]:
        dfs_wrong(graph, neighbor)  # visited 체크 없음
# 사이클 있는 그래프에서 무한 재귀

해결:

def dfs_correct(graph, node, visited):
    if node in visited:
        return
    
    visited.add(node)
    print(node)
    
    for neighbor in graph[node]:
        dfs_correct(graph, neighbor, visited)

문제 2: 방향 vs 무방향 혼동

증상:

# 무방향 그래프인데 한쪽만 추가
graph = {1: [2], 2: [3], 3: []}
# 1 → 2는 가능, 2 → 1은 불가능 (잘못됨)

해결:

# 무방향 그래프: 양방향 추가
def add_edge_undirected(graph, a, b):
    graph[a].append(b)
    graph[b].append(a)
# 방향 그래프: 한쪽만 추가
def add_edge_directed(graph, a, b):
    graph[a].append(b)

문제 3: 1-indexed vs 0-indexed

증상:

# 문제: 정점 1~N
# 코드: 0-indexed 사용
graph = {i: [] for i in range(n)}  # 0~N-1
# 정점 N이 누락됨

해결:

# 1-indexed
graph = {i: [] for i in range(1, n + 1)}
# 또는 0-indexed로 통일
edges = [[a - 1, b - 1] for a, b in edges]

문제 4: 메모리 초과 (인접 행렬)

증상:

n = 100000
matrix = [[0] * n for _ in range(n)]
# MemoryError: 10^10 크기 배열

해결: 인접 리스트 사용

graph = {i: [] for i in range(n)}
# O(V + E) 공간

마무리

그래프 자료구조는 연결 관계를 표현하는 가장 일반적인 구조입니다.

핵심 요약

  1. 표현
    • 인접 리스트: 희소 그래프 (O(V+E))
    • 인접 행렬: 밀집 그래프 (O(V²))
  2. 탐색
    • BFS: 최단 경로, 큐 사용
    • DFS: 모든 경로, 스택 사용
  3. 응용
    • 연결 요소, 사이클 감지, 위상 정렬

선택 가이드

상황표현탐색
간선 적음 (E << V²)인접 리스트BFS/DFS
간선 많음 (E ≈ V²)인접 행렬BFS/DFS
최단 경로인접 리스트BFS
모든 경로 나열인접 리스트DFS + 백트래킹 (방문 표시 해제)
간선 확인 빈번인접 행렬-

추천 문제

백준:

다음 단계

  • BFS와 DFS 상세: BFS와 DFS
  • 트리 자료구조: 트리
  • 백트래킹: 백트래킹 그래프는 실생활 문제를 모델링하는 핵심 도구입니다. BFS와 DFS에 익숙해지면 많은 그래프 문제를 해결할 수 있습니다.

자주 묻는 질문 (FAQ)

Q. 그래프 DFS가 끝나지 않고 무한 재귀에 빠지는 이유는 무엇인가요?

A. 트리와 달리 그래프에는 사이클이 있을 수 있어서, 방문 여부를 기록하지 않으면 A → B → A처럼 같은 정점을 계속 다시 방문합니다. 정점에 들어갈 때 visited 집합에 넣고, 이미 방문한 정점이면 바로 돌아오도록 해야 합니다. 무방향 그래프는 간선을 양쪽으로 저장하므로 사이클이 없어도 부모로 되돌아가는 경로가 생긴다는 점도 같이 기억해야 합니다.

같이 보면 좋은 글