📚 지식 노트

그래프와 그 표현

지하철 노선, 친구 관계, 웹 페이지의 링크, 빌드할 파일의 의존 관계, 게임 맵의 이동 가능한 칸은 모두 "무엇과 무엇이 이어져 있다"는 정보다. 이것을 점(vertex, 정점)과 간선(edge)으로 추상화한 것이 그래프(graph)다. 트리는 사이클이 없고 연결된 특별한 그래프다(트리 노트).

• 방향: 간선에 방향이 있으면 방향 그래프(directed graph, 일방통행·팔로우), 없으면 무방향 그래프(양방향 도로·친구).
• 가중치(weight): 간선마다 거리·시간·비용 같은 수가 붙으면 가중치 그래프다. 이 노트의 "최단"은 가중치 합이 가장 작다는 뜻이다.
• 차수(degree): 한 점에 붙은 간선 수. 방향 그래프는 들어오는 진입 차수와 나가는 진출 차수를 따로 센다.
• 사이클(cycle): 출발한 점으로 돌아오는 길. 방향 그래프에 사이클이 없으면 DAG(directed acyclic graph)라 부른다.
• 희소·조밀: 점 V개 그래프의 간선 수 E는 0부터 약 V²까지다. 실제 그래프는 대개 E가 V의 몇 배 정도인 희소 그래프다.

알고리즘의 속도는 그래프를 메모리에 어떻게 담느냐에 크게 달린다. 흔한 방법은 두 가지다. 인접 행렬(adjacency matrix)은 V×V 표의 (i, j) 칸에 간선 유무나 가중치를 적고, 인접 리스트(adjacency list)는 점마다 이웃 목록을 단다.

격자 맵처럼 이웃이 규칙적으로 정해지는 경우에는 그래프를 따로 만들지 않고 "(x, y)의 이웃은 상하좌우 네 칸"처럼 그때그때 계산하는 암묵적 그래프로 다루기도 한다.

문제 풀기 →Python 코드 →

너비 우선 탐색(BFS)

시작점에서 "간선을 가장 적게 지나서" 닿는 길을 찾고 싶다. 미로의 최단 경로, SNS의 "몇 다리 건너 아는 사이", 퍼즐의 최소 이동 횟수가 그렇다. 너비 우선 탐색(breadth-first search, BFS)은 시작점에서 가까운 점부터 한 겹씩 넓혀 간다. 도구는 먼저 넣은 것을 먼저 꺼내는 큐(queue)다.

visited = {s}; dist[s] = 0; queue = [s]
while queue가 비지 않음:
    u = queue.pop_front()
    for v in 이웃(u):
        if v not in visited:
            visited.add(v); dist[v] = dist[u] + 1
            queue.push_back(v)

큐에는 거리 d인 점들이 모두 나간 뒤에야 거리 d+1인 점들이 나온다. 그래서 어떤 점을 처음 발견한 순간 적은 거리가 곧 간선 수로 잰 최단 거리이고, 발견할 때 "어디서 왔는지"를 적어 두면 거꾸로 따라가 경로도 복원된다. 모든 점을 한 번씩 큐에 넣고 모든 간선을 한두 번 보므로 인접 리스트로 O(V + E)다.

• 방문 표시는 넣을 때: 꺼낼 때 표시하면 같은 점이 큐에 여러 번 들어가 시간과 메모리가 늘어난다.
• 가중치가 있으면 안 맞는다: 간선 수가 적은 길이 가중치 합도 작다는 보장이 없다. 가중치가 0과 1뿐이면 0인 간선은 큐 앞에, 1인 간선은 뒤에 넣는 0-1 BFS로 충분하고, 그 밖에는 다익스트라를 쓴다.
• 이분 그래프 판정: 시작점을 한 색으로 칠하고 이웃은 늘 반대 색으로 칠하며 BFS를 돈다. 이미 같은 색으로 칠해진 이웃을 만나면 홀수 길이 사이클이 있다는 뜻이라 이분 그래프가 아니다. 이분 그래프인 것과 홀수 사이클이 없는 것은 같은 말이고, 판정은 O(V + E)다.
• 쓰이는 곳: 격자 게임의 이동 범위 표시와 흐름장(flow field), 웹 크롤러의 링크 따라가기, 네트워크 방송, 이분 그래프 판정.

문제 풀기 →Python 코드 →

깊이 우선 탐색(DFS)

깊이 우선 탐색(depth-first search, DFS)은 반대로 한 갈래를 끝까지 파고든다. 이웃 하나로 들어가고, 그 점에서 또 안 가 본 이웃으로 들어가다가, 더 갈 곳이 없으면 한 칸 돌아와(백트래킹) 다른 이웃을 본다. 재귀 호출로 쓰면 호출 스택이 곧 "돌아갈 길"이 된다. 시간은 BFS와 같은 O(V + E)지만 최단 거리를 주지는 않는다. 대신 그래프의 구조를 드러낸다.

점마다 들어갈 때 발견 시각, 모든 이웃을 끝내고 나올 때 완료 시각을 적으면 두 점의 [발견, 완료] 구간은 서로 완전히 포개지거나(조상과 자손) 완전히 떨어진다(괄호 정리). 이 시각으로 간선을 나눌 수 있다. 아직 완료되지 않은 조상으로 돌아가는 간선이 역방향 간선(back edge)이고, 이것이 있으면 사이클이 있다.

• 사이클 찾기: 방향 그래프에서 스택에 걸린(진행 중인) 점으로 가는 간선을 만나면 사이클이다.
• 위상 정렬: DAG에서는 완료 시각이 늦은 순서가 그대로 위상 순서다. 그림 마지막 단계의 C, A, E, B, F, D가 그 예다.
• 연결 요소·강한 연결 요소: 아직 안 본 점에서 DFS를 새로 시작할 때마다 요소 하나가 나온다. 방향 그래프에서 서로 오갈 수 있는 묶음(SCC)은 타잔(Tarjan)이나 코사라주(Kosaraju) 알고리즘이 DFS 한두 번으로 찾는다.
• 깊은 재귀 주의: 점이 수십만 개인 한 줄 그래프에서는 재귀가 스택 넘침을 일으킨다. 실무에서는 명시적 스택으로 바꿔 쓴다.
• 쓰이는 곳: 미로 생성, 퍼즐의 백트래킹 탐색(알고리즘 기법 노트), 가비지 컬렉터의 도달 가능 객체 표시, 다리·단절점 찾기.

문제 풀기 →Python 코드 →

위상 정렬

"A를 하려면 먼저 B가 끝나야 한다" 같은 조건이 여럿 있을 때 모든 조건을 지키는 순서를 찾는 것이 위상 정렬(topological sort)이다. 선수 과목, 빌드 순서, 패키지 설치 순서, 스프레드시트 셀의 재계산 순서가 모두 그렇다. 의존 관계를 간선 B → A로 그리면, 모든 간선이 순서상 앞에서 뒤로 향하게 점을 한 줄로 세우는 문제가 된다. 사이클이 있으면 그런 순서는 없다.

칸 알고리즘(Kahn's algorithm)은 들어오는 간선이 없는(진입 차수 0인) 점은 지금 당장 해도 된다는 데서 출발한다. 그런 점을 하나 꺼내 순서에 붙이고, 그 점에서 나가는 간선을 지운다. 그러면 새로 진입 차수가 0이 되는 점이 생기고, 이를 큐가 빌 때까지 되풀이한다.

점과 간선을 한 번씩 다루므로 O(V + E)다. 큐가 비었는데 남은 점이 있으면 그 점들은 서로 물려 있는 사이클 안에 있다. 그래서 칸 알고리즘은 정렬과 사이클 검사를 한 번에 한다. 위상 순서는 대개 여러 개다. 큐에서 무엇을 먼저 꺼내느냐(예: 이름 순, 우선순위 순)로 그중 하나를 고른다.

DAG 위에서는 위상 순서대로 점을 한 번씩 보며 간선을 완화하면 음수 가중치가 있어도 최단·최장 경로를 O(V + E)에 구한다. 프로젝트 일정의 임계 경로(critical path) 계산이 이것이다. 이렇게 순서대로 작은 문제부터 푸는 방식은 동적 계획법과 같은 생각이다.

문제 풀기 →Python 코드 →

다익스트라: 가중치가 있는 최단 경로

도로마다 걸리는 시간이 다르면 BFS의 "간선 수"는 쓸모가 없다. 다익스트라 알고리즘(Dijkstra's algorithm, 1959)은 가중치가 음수가 아닐 때 한 출발점에서 모든 점까지의 최단 거리를 구한다. 거리표를 ∞로 채우고 출발점만 0으로 둔 뒤, 아직 확정되지 않은 점 가운데 거리가 가장 작은 점을 꺼내 확정하고, 그 점을 거쳐 가면 더 짧아지는 이웃의 거리를 고친다. 이 고치기를 완화(relaxation)라 한다.

dist[*] = ∞; dist[s] = 0; heap = [(0, s)]
while heap이 비지 않음:
    (d, u) = heap.pop_min()
    if d > dist[u]: continue        # 낡은 항목
    for (v, w) in 이웃(u):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w; prev[v] = u
            heap.push((dist[v], v))

꺼낸 점의 거리가 최종인 이유는 간선이 음수가 아니기 때문이다. 아직 남은 점들은 모두 지금 꺼낸 점보다 멀거나 같고, 그런 점을 거쳐 돌아오면 길이만 늘어난다. 음수 간선이 하나라도 있으면 이 논리가 깨져, 이미 확정한 거리가 나중에 더 줄어들 수 있다.

• 시간: 이진 힙이면 O((V + E) log V). 피보나치 힙은 이론상 O(E + V log V)지만 상수가 커서 실무에서는 이진 힙이 보통 더 빠르다. 점이 적고 조밀하면 힙 없이 배열을 훑는 O(V²)도 괜찮다.
• 음수를 상수로 덮으면 안 된다: 모든 간선에 같은 수 c를 더해 음수를 없애면, 간선 k개짜리 경로는 kc만큼 길어져 간선이 많은 길이 불리해진다. A→B가 −2, A→C가 1, C→B가 −4면 최단은 A→C→B(−3)지만, 모든 간선에 4를 더하면 A→B는 2, A→C→B는 5 + 0 = 5가 되어 답이 바뀐다. 존슨 알고리즘은 상수 대신 점마다 다른 퍼텐셜 h로 w(u, v) + h(u) − h(v)를 써서, 같은 두 점 사이의 모든 경로에 같은 양을 더하므로 최단 경로가 그대로 남는다.
• 낡은 항목: 거리가 줄 때마다 큐에 새 항목을 넣고, 꺼낼 때 이미 확정된 점이면 버린다(그림의 흐린 항목). 우선순위를 낮추는 연산 없이도 정확하다.
• 한 쌍만 필요하면: 목적지를 꺼내는 순간 멈춘다. 목적지 쪽으로 탐색을 기울이는 A*가 게임 길찾기의 표준이다(게임 AI 노트). 지도 서비스는 미리 지름길을 계산해 두는 기법(contraction hierarchies 등)을 더한다.
• 쓰이는 곳: 내비게이션, 링크 상태 라우팅 프로토콜 OSPF·IS-IS가 라우터마다 돌리는 최단 경로 계산(네트워크 노트).

문제 풀기 →Python 코드 →

벨먼-포드: 음수 간선과 음수 사이클

환율 차익, 보상이 있는 이동, 시간 제약처럼 가중치가 음수인 간선이 생기는 문제가 있다. 벨먼-포드 알고리즘(Bellman-Ford)은 똑똑하게 고르지 않는 대신 무식하게 반복한다. 모든 간선을 한 번씩 완화하는 바퀴를 V − 1번 돈다. 최단 경로는 사이클을 돌 이유가 없으므로 간선을 많아야 V − 1개 쓰고, k번째 바퀴가 끝나면 간선 k개 이하로 가는 최단 거리가 모두 구해지기 때문이다.

시간은 O(VE)로 다익스트라보다 훨씬 느리다. 한 바퀴 동안 아무것도 줄지 않으면 거기서 멈춰도 되고, 간선을 좋은 순서(출발점에서 가까운 것부터)로 보면 한두 바퀴에 끝나기도 한다. 직전 바퀴에 줄어든 점의 간선만 다시 보는 변형(SPFA)은 평균적으로 빠르지만 최악은 같다.

진짜 쓸모는 음수 사이클 검사다. 합이 음수인 사이클이 출발점에서 닿는 곳에 있으면 그 사이클을 돌수록 거리가 끝없이 줄어 "최단 거리"가 정의되지 않는다. V − 1바퀴 뒤에 한 바퀴를 더 돌았는데도 줄어드는 간선이 있으면 바로 그 경우다.

환율표에서 각 환율 r을 −log r 가중치로 바꾸면, 곱해서 1보다 커지는 환전 고리가 음수 사이클이 되어 차익 거래 탐지에 쓰인다. 옛 거리 벡터 라우팅 프로토콜 RIP도 이웃끼리 거리표를 주고받으며 벨먼-포드식 완화를 나눠서 한다.

문제 풀기 →Python 코드 →

플로이드-워셜: 모든 쌍의 최단 거리

모든 점 쌍의 거리가 필요하면 다익스트라를 점마다 돌려도 되지만, 점이 수백 개 이하로 적으면 플로이드-워셜(Floyd-Warshall)이 짧고 단단하다. 거리 행렬을 간선 가중치로 채운 뒤, 경유해도 되는 점을 1번, 2번, …으로 하나씩 늘려 가며 모든 칸에 "i → k → j가 i → j보다 짧으면 고친다"를 적용한다.

for k in 점:
    for i in 점:
        for j in 점:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

k번째 바퀴가 끝나면 dist[i][j]는 "1~k번 점만 거쳐 가는 최단 거리"가 된다. 이렇게 작은 문제의 답을 표에 쌓아 큰 문제를 푸는 동적 계획법의 전형이다. 반복 순서가 중요해 k가 바깥에 있어야 한다. 시간 O(V³), 메모리 O(V²)이고 음수 간선도 다룬다. 끝난 뒤 대각선 dist[i][i]가 음수인 점이 있으면 그 점은 음수 사이클 위에 있다.

간선 가중치를 "더하기·최소" 대신 "그리고·또는"으로 바꾸면 같은 세 겹 반복이 "i에서 j로 갈 수 있나"를 전부 구하는 이행적 폐쇄(transitive closure, 워셜 알고리즘)가 된다.

문제 풀기 →Python 코드 →

유니온 파인드

간선이 하나씩 추가될 때 "지금 u와 v가 이어져 있나"를 계속 묻는 문제가 있다. 매번 BFS를 돌리면 O(V + E)씩 든다. 유니온 파인드(union-find, 서로소 집합 자료구조 disjoint-set)는 두 연산만 아주 빠르게 한다. find(x)는 x가 속한 집합의 대표를 돌려주고, union(x, y)는 두 집합을 합친다. 두 원소의 대표가 같으면 같은 집합이다.

집합 하나를 트리 하나로, 대표를 그 뿌리로 둔다. 원소는 부모 번호만 기억하므로 배열 하나면 된다. 그냥 두면 트리가 한 줄로 길어질 수 있어 두 가지 장치를 단다.

• 랭크 기준 합치기(union by rank): 랭크(트리 높이의 상한)가 낮은 뿌리를 높은 뿌리 밑에 붙인다. 랭크가 같을 때만 높이가 1 는다. 이것만으로 높이가 O(log n)에 묶인다. 원소 수로 비교하는 크기 기준 합치기도 같은 효과다.
• 경로 압축(path compression): find가 뿌리까지 올라가며 지나온 원소를 모두 뿌리에 바로 붙인다. 다음에 그 원소들을 찾을 때는 한 걸음이면 된다.

둘을 함께 쓰면 연산 m번에 O(m·α(n))이 든다. α는 역 아커만 함수로, 우주의 원자 수만 한 n에도 4를 넘지 않아 사실상 상수다. 대신 "나누기"는 못 한다. 간선을 지우는 문제에는 다른 구조가 필요하다. 쓰이는 곳은 다음 절의 크루스칼, 이미지에서 이어진 픽셀 덩어리 찾기, 계정·기록 병합, 격자 미로가 뚫렸는지 보는 퍼콜레이션 판정 등이다.

문제 풀기 →Python 코드 →

최소 신장 트리: 크루스칼과 프림

마을 여러 곳을 전선이나 광케이블로 모두 잇되 총 길이를 가장 짧게 하고 싶다. 모든 점을 잇는 간선 V − 1개짜리 트리(신장 트리) 가운데 가중치 합이 가장 작은 것이 최소 신장 트리 (minimum spanning tree, MST)다. 출발점이 따로 없고 "전체 무게"를 줄인다는 점에서 최단 경로 트리와 다르다. 아래 예제에서는 MST(A–C, B–C, B–D, D–E, E–F)가 A에서 본 최단 경로 트리와 우연히 같지만, 늘 그렇지는 않다. A–B 2, A–C 2, B–C 1인 삼각형에서 A의 최단 경로 트리는 A–B와 A–C(무게 4)이고, MST는 B–C와 A–B(무게 3)다.

두 대표 알고리즘은 모두 자르기 성질(cut property)에 기댄다. 점들을 아무렇게나 두 무리로 나눴을 때, 두 무리를 잇는 간선 가운데 가장 가벼운 것은 어떤 MST에 반드시 들어 있다. 그러니 그런 간선을 고르는 탐욕(greedy) 선택이 안전하다.

크루스칼(Kruskal)은 간선을 가벼운 순으로 정렬해 하나씩 보며, 두 끝이 아직 다른 덩어리일 때만 고른다. "다른 덩어리인가"를 앞 절의 유니온 파인드가 거의 상수 시간에 답한다.

프림(Prim)은 한 점에서 트리를 키운다. 트리 안과 밖을 잇는 간선 가운데 가장 가벼운 것을 골라 바깥 점 하나를 트리에 들이고, 이를 V − 1번 되풀이한다. 후보 간선은 다익스트라처럼 우선순위 큐에 담는다. 다른 점은 큐의 열쇠가 "출발점까지 거리"가 아니라 "트리까지 간선 하나의 무게"라는 것뿐이다.

가중치가 모두 다르면 MST는 하나뿐이라 두 알고리즘이 같은 트리를 내고, 같은 값이 있으면 트리는 달라도 무게는 같다. 쓰이는 곳은 통신망·전력망 설계, 비슷한 점끼리 묶는 군집화(MST에서 가장 무거운 간선 몇 개를 끊는다), 외판원 문제의 근사 해법(알고리즘 너머 노트), 그리고 게임의 미로 생성이다. 격자 벽에 무작위 가중치를 주고 크루스칼이나 프림을 돌리면 모든 칸이 이어지되 사이클이 없는 완전 미로가 나온다.

문제 풀기 →Python 코드 →