수업 목표

본 수업은 방향 그래프의 강한 연결성과 지수 시간 알고리즘의 비트 최적화, 그리고 흐름과 배분 문제의 해법인 최대 유량 및 이분 매칭의 기본 원리를 완벽히 이해하고 파이썬으로 구현할 수 있는 역량을 배양하는 것을 목표로 합니다. - 타잔(Tarjan) 또는 코사라주(Kosaraju) 알고리즘을 활용하여 방향 그래프 내에서 서로 왕복 도달 가능한 정점들의 서브그룹(SCC)들을 $O(V+E)$에 완벽히 분리해냅니다. - 모든 정점을 정확히 한 번씩 방문하는 해밀턴 경로 문제를 비트마스크 동적 계획법을 통해 시간 복잡도를 $O(N!)$에서 $O(2^N \cdot N^2)$으로 단축시킵니다. - 에드몬즈-카프(Edmonds-Karp) 및 디닉(Dinic) 알고리즘을 통해 용량 제한이 있는 그래프에서의 최대 유량(Max Flow) 문제를 정형화하여 해결합니다. - 이분 그래프 상에서 서로 다른 두 정점 그룹을 겹치지 않게 최대로 매칭하는 이분 매칭(Bipartite Matching) 문제를 이해하고 증가 경로 탐색 기법을 학습합니다.

학습 동기부여

물류 인프라 전송망, 무선 통신 주파수 대역 배분, 대학의 강의 시간표 조율 등 현실 세계의 많은 공학 문제들은 유한한 자원을 겹치지 않게 효율적으로 나누고 이동 경로를 가시화하는 그래프 최적화 문제입니다. 방향성이 존재하는 복잡한 상호 관계 속에서 순환 고리(SCC)를 추려내어 논리적 인과관계를 일렬로 정리하고, 병목 구간이 어디인지(최대 유량)를 찾아내 문제를 개선하는 기술은 IT 대기업의 트래픽 라우팅 시스템과 스마트 물류망의 중심 뼈대를 형성합니다. 본 수업에서 다루는 개념들은 복잡한 인적/물적 자원의 최적 배치 효율성을 단 몇 초 만에 보장하는 핵심 알고리즘 도구들입니다.

도입 스토리

각 항로별로 보낼 수 있는 최대 컨테이너 개수가 다른 거대 해운 회사의 물류 유통 네트워크가 있습니다. 소스(시작 항구)에서 싱크(도착 항구)로 컨테이너를 가득 보내고 싶지만, 중간 경유지마다 배들의 적재 수량이 제약되어 있어 특정 항구에 화물이 가득 밀리는 병목 현상이 일어납니다. 직관에만 의존하여 무작정 짐을 싣는다면 흐름이 막혀 마비되겠지만, 증가 경로를 따라 유량을 흘리는 최대 유량 이론을 적용하면 전체 네트워크의 잠재 흐름 한계치를 $0.001$초 만에 산출하여 병목을 원천 해소할 수 있습니다. 그래프의 복잡한 흐름을 일괄적으로 제어하는 고급 그래프 알고리즘의 세계를 탐험해 봅시다.

1. 강한 연결 요소 (SCC)

유향 그래프에서 두 정점 $u, v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 항상 존재하는 부분 그래프를 강한 연결 요소(SCC)라고 합니다. 타잔(Tarjan) 알고리즘은 깊이 우선 탐색(DFS)을 1회 수행하는 과정에서 방문 순서 인덱스를 스택에 넣어 보존하면서 역방향 간선이 이미 방문한 스택 내 조상을 가리키고 있는지 판별하여 $O(V+E)$에 모든 SCC를 식별해 냅니다.

# 8061번: 강한 연결 요소 — Tarjan's SCC O(V+E) 알고리즘
import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline

def solve_scc():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        
    visited = [0] * (n + 1)
    low = [0] * (n + 1)
    in_stack = [False] * (n + 1)
    stack = []
    timer = 0
    sccs = []
    
    def dfs(u):
        nonlocal timer
        timer += 1
        visited[u] = timer
        low[u] = timer
        stack.append(u)
        in_stack[u] = True
        
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif in_stack[v]:
                low[u] = min(low[u], visited[v])
                
        if low[u] == visited[u]:
            scc = []
            while True:
                curr = stack.pop()
                in_stack[curr] = False
                scc.append(curr)
                if curr == u:
                    break
            scc.sort()
            sccs.append(scc)
            
    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i)
            
    sccs.sort(key=lambda x: x[0])
    print(len(sccs))
    for scc in sccs:
        print(*(scc), -1)

solve_scc()

2. 해밀턴 경로와 비트마스크 DP

해밀턴 경로(Hamiltonian Path)는 그래프의 모든 정점을 정확히 한 번씩만 방문하는 경로입니다. 일반적인 순열 백트래킹 탐색은 $O(N!)$이 되어 정점이 15개 이상인 경우 연산이 불가하지만, 비트마스크를 활용하여 이미 방문한 정점 상태를 정수로 압축하면 $O(2^N \cdot N^2)$에 연산이 가능합니다.

# 8062번: 해밀턴 경로 — Bitmask DP O(2^N * N^2) 알고리즘
import sys
input = sys.stdin.readline

def solve_hamilton():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        
    MOD = 1000000007
    # dp[mask][u] : 방문한 정점 비트가 mask이고, 현재 u에 위치한 경로의 수
    dp = [[0] * (n + 1) for _ in range(1 << n)]
    dp[1][1] = 1 # 1번 방에서 출발
    
    for mask in range(1, 1 << n):
        for u in range(1, n + 1):
            if not dp[mask][u]:
                continue
            # 만약 마지막 방에 도달했다면 탐색 중지 (더 이상 이동하지 않음)
            if u == n:
                continue
            for v in adj[u]:
                if not (mask & (1 << (v - 1))):
                    next_mask = mask | (1 << (v - 1))
                    dp[next_mask][v] = (dp[next_mask][v] + dp[mask][u]) % MOD
                    
    print(dp[(1 << n) - 1][n])

solve_hamilton()

3. 네트워크 유량 - 에드몬즈-카프 알고리즘

최대 유량(Max Flow)을 구하기 위해 BFS를 반복 사용하여 최단 증가 경로(Augmenting Path)를 찾는 기법이 에드몬즈-카프(Edmonds-Karp) 알고리즘입니다. 매 단계 역방향 간선에 가상의 유량(Residual Flow)을 대칭적으로 차감 및 누적시켜, 흘렸던 물줄기를 되돌리며 최적의 전송량을 찾을 수 있게 설계합니다.

# 8063번: 최대 유량 — Edmonds-Karp O(V * E^2) 알고리즘
from collections import deque
import sys
input = sys.stdin.readline
INF = float('inf')

def solve_maxflow():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    capacity = {}
    
    for _ in range(m):
        u, v, c = map(int, input().split())
        if (u, v) not in capacity:
            capacity[(u, v)] = 0
            capacity[(v, u)] = 0
            adj[u].append(v)
            adj[v].append(u)
        capacity[(u, v)] += c
        
    flow = 0
    while True:
        parent = [-1] * (n + 1)
        parent[1] = -2
        q = deque([1])
        
        while q:
            curr = q.popleft()
            for nxt in adj[curr]:
                if parent[nxt] == -1 and capacity[(curr, nxt)] > 0:
                    parent[nxt] = curr
                    if nxt == n:
                        break
                    q.append(nxt)
            if parent[n] != -1:
                break
                
        if parent[n] == -1:
            break
            
        # 최대로 흘릴 수 있는 병목 용량 탐색
        curr_flow = INF
        v = n
        while v != 1:
            u = parent[v]
            curr_flow = min(curr_flow, capacity[(u, v)])
            v = u
            
        # 잔여 용량 및 역방향 에지 용량 수정
        v = n
        while v != 1:
            u = parent[v]
            capacity[(u, v)] -= curr_flow;
            capacity[(v, u)] += curr_flow;
            v = u
            
        flow += curr_flow
        
    print(flow)

solve_maxflow()

4. 이분 매칭 (Bipartite Matching)

이분 그래프의 한 그룹 A와 다른 그룹 B 간에 중복 없이 매칭 쌍을 조율하는 알고리즘입니다. 증가 경로를 발견하면 기존 매칭 관계를 DFS 재귀적으로 재배정(Augmenting Path)하는 방식을 사용해 $O(V E)$에 완벽한 매칭 관계를 구축할 수 있습니다.

# 8064번: 이분 매칭 — DFS 증가경로 매칭 알고리즘
import sys
input = sys.stdin.readline

def solve_matching():
    n, m, k = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(k):
        u, v = map(int, input().split())
        adj[u].append(v)
        
    match = [-1] * (m + 1)
    
    def dfs(u):
        for v in adj[u]:
            if visited[v]:
                continue
            visited[v] = True
            if match[v] < 0 or dfs(match[v]):
                match[v] = u
                return True
        return False
        
    count = 0
    for i in range(1, n + 1):
        visited = [False] * (m + 1)
        if dfs(i):
            count += 1
            
    print(count)

solve_matching()

자주 하는 실수 & 오류 예방

- Tarjan DFS 재귀 한계 해제: 파이썬은 기본 재귀 제한이 1000이므로 5000 노드 규모의 방향 그래프 DFS 시 깊이 오버플로우가 생깁니다. 반드시 코드 도입부에 sys.setrecursionlimit(20000)을 명시하십시오. - 해밀턴 비행 N번 노드 종단 조건: 해밀턴 경로 문제 해결 시 N번 노드에 이미 닿아있는 상태에서 루프가 지속적으로 전이되게 하면 다른 노드를 거치고 오는 오답 경로가 중복 계산됩니다. u == n 일 때 즉시 루프를 건너뛰는(continue) 예외를 두어야 합니다. - 양방향 인접 리스트의 유량 소모: 에드몬즈-카프 알고리즘 진행 시 잔여 그래프 처리를 위해 capacity[(v, u)] 역방향 간선을 만들 때 무작정 capacity 값을 주면 안 되고 초깃값을 0으로 둔 채 갱신해야 순수한 유량 흐름만 제어됩니다.

핵심 정리

알고리즘 및 주제	시간 복잡도	공간 복잡도	주요 아이디어	활용 도메인
Tarjan's SCC	$O(V + E)$	$O(V)$	DFS 1회 탐색과 방문 순서(Visited) & 스택 보존	소셜 그룹 응집성 검사, 2-SAT 논리 검증
비트마스크 DP 해밀턴	$O(2^N \cdot N^2)$	$O(2^N \cdot N)$	방문 상태를 2진 비트 정보로 압축하여 중복 연산 차단	외판원 문제(TSP), 순서 종속 스케줄링
에드몬즈-카프 최대 유량	$O(V E^2)$	$O(V + E)$	BFS 기반 최단 경로에 따른 유량 전송 및 가상 역류 반영	네트워크 용량 배분, 컷-유량 이중성 컷 분석
이분 매칭 (Augmenting DFS)	$O(V E)$	$O(V)$	DFS 기반 기존 매칭 양보 및 증가 매칭 탐색	작업 분배, 매칭 기반 추천 매핑

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8061	강한 연결 요소	CSES	어려움	타잔/코사라주 SCC 분류
8062	해밀턴 경로	CSES	어려움	비트마스크 & 동적 계획법
8063	최대 유량	CSES	어려움	에드몬즈-카프/디닉 알고리즘
8064	이분 매칭	CSES	보통	DFS 매칭 / 최대 유량 변환