[CS 기초 #9] 그래프: 현실 세계를 모델링하는 강력한 자료구조

세상의 모든 연결을 표현합니다! 소셜 네트워크부터 지도 내비게이션까지, 그래프는 어디에나 있습니다.

🎯 이 글을 읽고 나면

• 그래프의 개념과 용어(정점, 간선, 차수)를 이해합니다
• 인접 행렬과 인접 리스트의 차이를 설명할 수 있습니다
• DFS와 BFS를 구현하고 차이를 설명할 수 있습니다
• 다익스트라 알고리즘으로 최단 경로를 찾을 수 있습니다
• 소셜 네트워크, 지도 등 실제 응용 사례를 이해합니다

📚 사전 지식

• 스택과 큐: 이전 글: 스택과 큐 - DFS/BFS에 필수
• 재귀 함수: DFS 구현에 필요
• 우선순위 큐: 다익스트라 알고리즘에 사용

💡 핵심 개념 미리보기

그래프는 정점(Vertex)과 간선(Edge)으로 현실 세계의 연결 관계를 표현합니다. 친구 관계, 도로망, 웹 페이지 링크 등이 모두 그래프입니다. DFS/BFS로 탐색하고, 다익스트라로 최단 경로를 찾으며, Union-Find로 연결 요소를 판별합니다!

---

🌐 들어가며: 그래프는 어디서 사용될까?

소셜 네트워크, 지도 내비게이션, 추천 시스템, 네트워크 라우팅… 우리 주변의 모든 연결 관계는 그래프로 표현됩니다!

오늘은 현실 세계의 복잡한 관계를 모델링하는 그래프(Graph) 자료구조와 핵심 알고리즘들을 깊이 있게 알아보겠습니다. DFS, BFS부터 최단 경로, 최소 신장 트리까지 모두 다룹니다!

📊 그래프의 기본 개념

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.

graph LR
    A[정점 A] --- B[정점 B]
    B --- C[정점 C]
    C --- D[정점 D]
    D --- A
    B --- D
    A --- E[정점 E]
    E --- D

그래프 용어 정리

class GraphTerminology:
    """그래프 용어 설명"""
    
    def __init__(self):
        self.terms = {
            "정점(Vertex)": "노드라고도 하며, 그래프의 기본 단위",
            "간선(Edge)": "정점들을 연결하는 선",
            "인접(Adjacent)": "간선으로 직접 연결된 정점들",
            "차수(Degree)": "정점에 연결된 간선의 수",
            "경로(Path)": "정점들의 연속된 연결",
            "사이클(Cycle)": "시작과 끝이 같은 경로",
            "연결 그래프": "모든 정점이 연결된 그래프",
            "가중치(Weight)": "간선에 부여된 값",
            "방향 그래프": "간선에 방향이 있는 그래프",
            "무방향 그래프": "간선에 방향이 없는 그래프",
            "완전 그래프": "모든 정점이 서로 연결된 그래프",
            "부분 그래프": "원래 그래프의 일부",
            "신장 트리": "모든 정점을 포함하는 트리"
        }
    
    def print_terms(self):
        for term, description in self.terms.items():
            print(f"• {term}: {description}")

terminology = GraphTerminology()
terminology.print_terms()

🔗 그래프 표현 방법

1. 인접 행렬 (Adjacency Matrix)

class GraphMatrix:
    """인접 행렬로 표현한 그래프"""
    
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, u, v, weight=1):
        """간선 추가 (무방향 그래프)"""
        self.graph[u][v] = weight
        self.graph[v][u] = weight  # 무방향 그래프
    
    def add_directed_edge(self, u, v, weight=1):
        """방향 간선 추가"""
        self.graph[u][v] = weight
    
    def remove_edge(self, u, v):
        """간선 제거"""
        self.graph[u][v] = 0
        self.graph[v][u] = 0
    
    def has_edge(self, u, v):
        """간선 존재 확인 - O(1)"""
        return self.graph[u][v] != 0
    
    def get_neighbors(self, v):
        """인접 정점 반환 - O(V)"""
        neighbors = []
        for i in range(self.V):
            if self.graph[v][i] != 0:
                neighbors.append(i)
        return neighbors
    
    def print_matrix(self):
        """행렬 출력"""
        print("인접 행렬:")
        print("  ", end="")
        for i in range(self.V):
            print(f"{i:2}", end=" ")
        print()
        
        for i in range(self.V):
            print(f"{i:2}", end=" ")
            for j in range(self.V):
                print(f"{self.graph[i][j]:2}", end=" ")
            print()

# 인접 행렬 테스트
gm = GraphMatrix(5)
edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
for u, v in edges:
    gm.add_edge(u, v)

gm.print_matrix()
print(f"\n정점 1의 이웃: {gm.get_neighbors(1)}")

2. 인접 리스트 (Adjacency List)

from collections import defaultdict

class GraphList:
    """인접 리스트로 표현한 그래프"""
    
    def __init__(self):
        self.graph = defaultdict(list)
        self.weights = {}  # 가중치 저장
    
    def add_edge(self, u, v, weight=1):
        """간선 추가 (무방향 그래프)"""
        self.graph[u].append(v)
        self.graph[v].append(u)
        self.weights[(u, v)] = weight
        self.weights[(v, u)] = weight
    
    def add_directed_edge(self, u, v, weight=1):
        """방향 간선 추가"""
        self.graph[u].append(v)
        self.weights[(u, v)] = weight
    
    def remove_edge(self, u, v):
        """간선 제거"""
        if v in self.graph[u]:
            self.graph[u].remove(v)
        if u in self.graph[v]:
            self.graph[v].remove(u)
        
        if (u, v) in self.weights:
            del self.weights[(u, v)]
        if (v, u) in self.weights:
            del self.weights[(v, u)]
    
    def has_edge(self, u, v):
        """간선 존재 확인 - O(degree)"""
        return v in self.graph[u]
    
    def get_neighbors(self, v):
        """인접 정점 반환 - O(1)"""
        return self.graph[v]
    
    def get_weight(self, u, v):
        """간선 가중치 반환"""
        return self.weights.get((u, v), 0)
    
    def print_list(self):
        """리스트 출력"""
        print("인접 리스트:")
        for vertex in sorted(self.graph.keys()):
            neighbors = self.graph[vertex]
            print(f"{vertex}: {neighbors}")

# 인접 리스트 테스트
gl = GraphList()
edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
for u, v in edges:
    gl.add_edge(u, v)

gl.print_list()

🔍 그래프 탐색

DFS (깊이 우선 탐색)

class DFS:
    """깊이 우선 탐색"""
    
    def __init__(self, graph):
        self.graph = graph
        self.visited = set()
    
    def dfs_recursive(self, vertex, result=None):
        """재귀적 DFS"""
        if result is None:
            result = []
        
        self.visited.add(vertex)
        result.append(vertex)
        
        for neighbor in self.graph[vertex]:
            if neighbor not in self.visited:
                self.dfs_recursive(neighbor, result)
        
        return result
    
    def dfs_iterative(self, start):
        """반복적 DFS (스택 사용)"""
        visited = set()
        stack = [start]
        result = []
        
        while stack:
            vertex = stack.pop()
            
            if vertex not in visited:
                visited.add(vertex)
                result.append(vertex)
                
                # 역순으로 추가 (왼쪽부터 방문하기 위해)
                for neighbor in reversed(self.graph[vertex]):
                    if neighbor not in visited:
                        stack.append(neighbor)
        
        return result
    
    def find_all_paths(self, start, end, path=None):
        """모든 경로 찾기"""
        if path is None:
            path = []
        
        path = path + [start]
        
        if start == end:
            return [path]
        
        paths = []
        for neighbor in self.graph[start]:
            if neighbor not in path:
                new_paths = self.find_all_paths(neighbor, end, path)
                paths.extend(new_paths)
        
        return paths
    
    def has_cycle(self):
        """사이클 검출 (무방향 그래프)"""
        visited = set()
        
        def dfs_cycle(vertex, parent):
            visited.add(vertex)
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    if dfs_cycle(neighbor, vertex):
                        return True
                elif parent != neighbor:
                    return True
            
            return False
        
        for vertex in self.graph:
            if vertex not in visited:
                if dfs_cycle(vertex, -1):
                    return True
        
        return False

# DFS 테스트
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}

dfs = DFS(graph)
print(f"DFS 재귀: {dfs.dfs_recursive(0)}")
print(f"DFS 반복: {dfs.dfs_iterative(0)}")
print(f"0→5 모든 경로: {dfs.find_all_paths(0, 5)}")
print(f"사이클 존재: {dfs.has_cycle()}")

BFS (너비 우선 탐색)

from collections import deque

class BFS:
    """너비 우선 탐색"""
    
    def __init__(self, graph):
        self.graph = graph
    
    def bfs(self, start):
        """BFS 탐색"""
        visited = set([start])
        queue = deque([start])
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return result
    
    def bfs_level_order(self, start):
        """레벨별 BFS"""
        visited = set([start])
        queue = deque([(start, 0)])
        levels = defaultdict(list)
        
        while queue:
            vertex, level = queue.popleft()
            levels[level].append(vertex)
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, level + 1))
        
        return dict(levels)
    
    def shortest_path(self, start, end):
        """최단 경로 (무가중치)"""
        visited = set([start])
        queue = deque([(start, [start])])
        
        while queue:
            vertex, path = queue.popleft()
            
            if vertex == end:
                return path
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, path + [neighbor]))
        
        return None
    
    def is_bipartite(self):
        """이분 그래프 판별"""
        color = {}
        
        for start in self.graph:
            if start not in color:
                queue = deque([start])
                color[start] = 0
                
                while queue:
                    vertex = queue.popleft()
                    
                    for neighbor in self.graph[vertex]:
                        if neighbor not in color:
                            color[neighbor] = 1 - color[vertex]
                            queue.append(neighbor)
                        elif color[neighbor] == color[vertex]:
                            return False
        
        return True

# BFS 테스트
bfs = BFS(graph)
print(f"BFS: {bfs.bfs(0)}")
print(f"레벨별 BFS: {bfs.bfs_level_order(0)}")
print(f"최단 경로 0→5: {bfs.shortest_path(0, 5)}")
print(f"이분 그래프: {bfs.is_bipartite()}")

🛤️ 최단 경로 알고리즘

다익스트라 알고리즘 (Dijkstra’s Algorithm)

import heapq

class Dijkstra:
    """다익스트라 최단 경로 알고리즘"""
    
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v, weight):
        """간선 추가"""
        self.graph[u].append((v, weight))
    
    def dijkstra(self, start):
        """다익스트라 알고리즘 - O((V + E) log V)"""
        # 거리 초기화
        dist = [float('inf')] * self.V
        dist[start] = 0
        
        # 이전 노드 추적
        prev = [None] * self.V
        
        # 우선순위 큐 (거리, 정점)
        pq = [(0, start)]
        visited = set()
        
        while pq:
            current_dist, u = heapq.heappop(pq)
            
            if u in visited:
                continue
            
            visited.add(u)
            
            # 인접 정점 확인
            for v, weight in self.graph[u]:
                if v not in visited:
                    new_dist = current_dist + weight
                    
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        prev[v] = u
                        heapq.heappush(pq, (new_dist, v))
        
        return dist, prev
    
    def get_path(self, prev, end):
        """경로 복원"""
        path = []
        current = end
        
        while current is not None:
            path.append(current)
            current = prev[current]
        
        return path[::-1] if path[0] is not None else []
    
    def dijkstra_all_paths(self, start):
        """모든 정점까지의 최단 경로"""
        dist, prev = self.dijkstra(start)
        paths = {}
        
        for vertex in range(self.V):
            if dist[vertex] != float('inf'):
                paths[vertex] = {
                    'distance': dist[vertex],
                    'path': self.get_path(prev, vertex)
                }
        
        return paths

# 다익스트라 테스트
dijkstra = Dijkstra(6)
edges = [
    (0, 1, 4), (0, 2, 3),
    (1, 2, 1), (1, 3, 2),
    (2, 3, 4),
    (3, 4, 2), (3, 5, 6),
    (4, 5, 3)
]

for u, v, w in edges:
    dijkstra.add_edge(u, v, w)
    dijkstra.add_edge(v, u, w)  # 무방향 그래프

paths = dijkstra.dijkstra_all_paths(0)
for vertex, info in paths.items():
    print(f"0 → {vertex}: 거리={info['distance']}, 경로={info['path']}")

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

class BellmanFord:
    """벨만-포드 알고리즘 (음수 가중치 허용)"""
    
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []
    
    def add_edge(self, u, v, weight):
        """간선 추가"""
        self.edges.append((u, v, weight))
    
    def bellman_ford(self, start):
        """벨만-포드 알고리즘 - O(VE)"""
        # 거리 초기화
        dist = [float('inf')] * self.V
        dist[start] = 0
        prev = [None] * self.V
        
        # V-1번 반복
        for _ in range(self.V - 1):
            for u, v, weight in self.edges:
                if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    prev[v] = u
        
        # 음수 사이클 검출
        for u, v, weight in self.edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                print("음수 사이클 발견!")
                return None, None
        
        return dist, prev

# 벨만-포드 테스트
bf = BellmanFord(5)
edges = [
    (0, 1, -1), (0, 2, 4),
    (1, 2, 3), (1, 3, 2), (1, 4, 2),
    (3, 2, 5), (3, 1, 1),
    (4, 3, -3)
]

for u, v, w in edges:
    bf.add_edge(u, v, w)

dist, prev = bf.bellman_ford(0)
if dist:
    print("벨만-포드 최단 거리:")
    for i in range(5):
        print(f"0 → {i}: {dist[i]}")

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

class FloydWarshall:
    """플로이드-워셜 알고리즘 (모든 쌍 최단 경로)"""
    
    def __init__(self, vertices):
        self.V = vertices
        self.dist = [[float('inf')] * vertices for _ in range(vertices)]
        
        # 자기 자신까지의 거리는 0
        for i in range(vertices):
            self.dist[i][i] = 0
    
    def add_edge(self, u, v, weight):
        """간선 추가"""
        self.dist[u][v] = weight
    
    def floyd_warshall(self):
        """플로이드-워셜 알고리즘 - O(V³)"""
        # 경로 추적을 위한 배열
        next_vertex = [[None] * self.V for _ in range(self.V)]
        
        # 직접 연결된 간선 초기화
        for i in range(self.V):
            for j in range(self.V):
                if i != j and self.dist[i][j] != float('inf'):
                    next_vertex[i][j] = j
        
        # 모든 정점을 중간 정점으로 고려
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.dist[i][k] + self.dist[k][j] < self.dist[i][j]:
                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]
                        next_vertex[i][j] = next_vertex[i][k]
        
        return self.dist, next_vertex
    
    def get_path(self, next_vertex, start, end):
        """경로 복원"""
        if next_vertex[start][end] is None:
            return []
        
        path = [start]
        while start != end:
            start = next_vertex[start][end]
            path.append(start)
        
        return path
    
    def print_solution(self):
        """결과 출력"""
        dist, next_vertex = self.floyd_warshall()
        
        print("최단 거리 행렬:")
        for i in range(self.V):
            for j in range(self.V):
                if dist[i][j] == float('inf'):
                    print("INF", end="\t")
                else:
                    print(f"{dist[i][j]:3}", end="\t")
            print()

# 플로이드-워셜 테스트
fw = FloydWarshall(4)
edges = [
    (0, 1, 5), (0, 3, 10),
    (1, 2, 3),
    (2, 3, 1)
]

for u, v, w in edges:
    fw.add_edge(u, v, w)

fw.print_solution()

🌲 최소 신장 트리 (MST)

크루스칼 알고리즘 (Kruskal’s Algorithm)

class UnionFind:
    """Union-Find 자료구조"""
    
    def __init__(self, vertices):
        self.parent = list(range(vertices))
        self.rank = [0] * vertices
    
    def find(self, x):
        """Find with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """Union by rank"""
        px, py = self.find(x), self.find(y)
        
        if px == py:
            return False
        
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        
        return True

class Kruskal:
    """크루스칼 알고리즘"""
    
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []
    
    def add_edge(self, u, v, weight):
        """간선 추가"""
        self.edges.append((weight, u, v))
    
    def kruskal_mst(self):
        """크루스칼 알고리즘 - O(E log E)"""
        # 간선을 가중치 순으로 정렬
        self.edges.sort()
        
        uf = UnionFind(self.V)
        mst = []
        total_weight = 0
        
        for weight, u, v in self.edges:
            if uf.union(u, v):
                mst.append((u, v, weight))
                total_weight += weight
                
                if len(mst) == self.V - 1:
                    break
        
        return mst, total_weight

# 크루스칼 테스트
kruskal = Kruskal(5)
edges = [
    (0, 1, 2), (0, 3, 6),
    (1, 2, 3), (1, 3, 8), (1, 4, 5),
    (2, 4, 7),
    (3, 4, 9)
]

for u, v, w in edges:
    kruskal.add_edge(u, v, w)

mst, total = kruskal.kruskal_mst()
print("크루스칼 MST:")
for u, v, w in mst:
    print(f"  {u} - {v}: {w}")
print(f"총 가중치: {total}")

프림 알고리즘 (Prim’s Algorithm)

class Prim:
    """프림 알고리즘"""
    
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v, weight):
        """간선 추가"""
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))
    
    def prim_mst(self):
        """프림 알고리즘 - O(E log V)"""
        visited = set([0])  # 0번 정점부터 시작
        mst = []
        total_weight = 0
        
        # 우선순위 큐 (가중치, 시작 정점, 끝 정점)
        edges = []
        for v, weight in self.graph[0]:
            heapq.heappush(edges, (weight, 0, v))
        
        while edges and len(visited) < self.V:
            weight, u, v = heapq.heappop(edges)
            
            if v not in visited:
                visited.add(v)
                mst.append((u, v, weight))
                total_weight += weight
                
                # 새로 추가된 정점의 간선들 추가
                for next_v, next_weight in self.graph[v]:
                    if next_v not in visited:
                        heapq.heappush(edges, (next_weight, v, next_v))
        
        return mst, total_weight

# 프림 테스트
prim = Prim(5)
edges = [
    (0, 1, 2), (0, 3, 6),
    (1, 2, 3), (1, 3, 8), (1, 4, 5),
    (2, 4, 7),
    (3, 4, 9)
]

for u, v, w in edges:
    prim.add_edge(u, v, w)

mst, total = prim.prim_mst()
print("\n프림 MST:")
for u, v, w in mst:
    print(f"  {u} - {v}: {w}")
print(f"총 가중치: {total}")

🔄 위상 정렬 (Topological Sort)

class TopologicalSort:
    """위상 정렬"""
    
    def __init__(self):
        self.graph = defaultdict(list)
        self.in_degree = defaultdict(int)
    
    def add_edge(self, u, v):
        """방향 간선 추가"""
        self.graph[u].append(v)
        self.in_degree[v] += 1
        if u not in self.in_degree:
            self.in_degree[u] = 0
    
    def kahn_algorithm(self):
        """칸 알고리즘 (BFS 기반) - O(V + E)"""
        # 진입 차수가 0인 정점들
        queue = deque([v for v in self.in_degree if self.in_degree[v] == 0])
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            for neighbor in self.graph[vertex]:
                self.in_degree[neighbor] -= 1
                if self.in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        # 사이클 검출
        if len(result) != len(self.in_degree):
            return None  # 사이클 존재
        
        return result
    
    def dfs_topological_sort(self):
        """DFS 기반 위상 정렬 - O(V + E)"""
        visited = set()
        stack = []
        
        def dfs(vertex):
            visited.add(vertex)
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    dfs(neighbor)
            
            stack.append(vertex)
        
        # 모든 정점에서 DFS 시작
        for vertex in list(self.graph.keys()) + list(self.in_degree.keys()):
            if vertex not in visited:
                dfs(vertex)
        
        return stack[::-1]

# 위상 정렬 테스트 (과목 수강 순서)
ts = TopologicalSort()
prerequisites = [
    ("미적분", "선형대수"),
    ("미적분", "확률통계"),
    ("프로그래밍", "자료구조"),
    ("자료구조", "알고리즘"),
    ("선형대수", "머신러닝"),
    ("확률통계", "머신러닝"),
    ("알고리즘", "머신러닝")
]

for pre, course in prerequisites:
    ts.add_edge(pre, course)

result = ts.kahn_algorithm()
if result:
    print("수강 순서 (칸 알고리즘):")
    for i, course in enumerate(result, 1):
        print(f"{i}. {course}")

💡 실전 문제 풀이

문제 1: 섬의 개수

def num_islands(grid):
    """섬의 개수 세기 (DFS)"""
    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 or grid[r][c] == '0':
            return
        
        grid[r][c] = '0'  # 방문 표시
        
        # 상하좌우 탐색
        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':
                count += 1
                dfs(r, c)
    
    return count

# 테스트
grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
print(f"섬의 개수: {num_islands(grid)}")

문제 2: 친구 네트워크

class FriendNetwork:
    """친구 네트워크 (Union-Find)"""
    
    def __init__(self):
        self.parent = {}
        self.size = {}
    
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.size[x] = 1
        
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        
        if px == py:
            return self.size[px]
        
        if self.size[px] < self.size[py]:
            px, py = py, px
        
        self.parent[py] = px
        self.size[px] += self.size[py]
        
        return self.size[px]
    
    def add_friendship(self, person1, person2):
        """친구 관계 추가"""
        network_size = self.union(person1, person2)
        print(f"{person1}와 {person2}가 친구가 되었습니다. 네트워크 크기: {network_size}")

# 테스트
network = FriendNetwork()
friendships = [
    ("Alice", "Bob"),
    ("Bob", "Charlie"),
    ("David", "Eve"),
    ("Alice", "David"),
    ("Frank", "George")
]

for p1, p2 in friendships:
    network.add_friendship(p1, p2)

🎯 핵심 정리

꼭 기억해야 할 5가지

1. 그래프는 정점과 간선으로 관계를 표현
2. DFS는 깊이 우선, BFS는 너비 우선
3. 다익스트라는 양수 가중치 최단 경로
4. MST는 모든 정점을 최소 비용으로 연결
5. 위상 정렬은 선후 관계가 있는 작업 순서

실무 활용 팁

• 최단 경로 → 다익스트라, 벨만-포드
• 모든 연결 → MST (크루스칼, 프림)
• 작업 순서 → 위상 정렬
• 네트워크 분석 → Union-Find

📚 추가 학습 자료

추천 문제

• LeetCode: Number of Islands, Course Schedule, Network Delay Time
• 프로그래머스: 네트워크, 가장 먼 노드, 순위
• 백준: 1260(DFS와 BFS), 1753(최단경로), 1197(최소 스패닝 트리)

🚀 다음 시간 예고

다음 포스트에서는 자료구조편의 마지막, 해시 테이블(Hash Table)을 다룹니다. O(1) 검색의 비밀을 알아보겠습니다!

---

📌 시리즈 네비게이션

순서	제목	링크
8	트리 구조: 이진 트리부터 B-트리까지	← 이전 글
9	그래프: 현실 세계를 모델링하는 방법 ✅	현재 글
10	해시 테이블: O(1) 검색의 비밀	다음 글 →

📋 전체 시리즈 목차 보기

기초 이론편

1. CS 입문 ✅
2. 컴퓨터 구조 ✅
3. 이진수와 논리 게이트 ✅
4. 운영체제 기초 ✅
5. 네트워크 기초 ✅

자료구조편

1. 배열과 연결 리스트 ✅
2. 스택과 큐 ✅
3. 트리 구조 ✅
4. 그래프 ✅
5. 해시 테이블

알고리즘편

1. 복잡도 분석
2. 정렬 알고리즘
3. 탐색 알고리즘
4. 동적 계획법
5. 그리디와 분할정복

실무 응용편

1. 데이터베이스 이론
2. 소프트웨어 공학
3. 보안 기초
4. 분산 시스템
5. CS 종합과 면접 준비