📚 지식 노트

행렬은 아래와 같고, 리스트는 A: B, C / B: D / C: F / D: E / E: B / F: E다. 진출 차수는 행의 합, 진입 차수는 열의 합이다.

열 순서는 A~F다. B와 E 열에 1이 둘씩 있어 진입 차수가 2이고, A 행에 1이 둘이라 A의 진출 차수가 2다. 칸 36개 가운데 1은 7개뿐이다. 리스트는 간선 7개만 적으니 이런 희소 그래프에서 훨씬 작다.

차수는 A 2, B 2, C 2, D 3, E 1이고, 간선은 5개다.

차수는 행(또는 열)의 1 개수다. 간선 하나가 양 끝 두 점의 차수를 하나씩 올리므로 차수의 합은 간선 수의 두 배다(2 + 2 + 2 + 3 + 1 = 10 = 2 × 5). 행렬에서도 1이 10개, 간선마다 대칭으로 두 칸이다.

인접 행렬은 약 125GB, 인접 리스트는 약 400MB다.

행렬은 V² = 10¹²칸이고 1비트씩이면 10¹² / 8 = 1.25 × 10¹¹바이트, 125GB다. 친구 관계는 방향이 없어 간선 E = 100만 × 100 / 2 = 5,000만 개이고, 리스트는 간선마다 양쪽에 한 번씩 2E = 1억 항목 × 4바이트 = 400MB다(점마다 리스트 시작 위치 몇 MB가 더 든다). 칸의 99.99%가 0인 행렬은 낭비다. 실제 그래프는 이렇게 희소하므로 대부분 리스트를 쓴다.

D가 큐에 두 번 들어간다. B를 꺼낼 때 D를 넣고, C를 꺼낼 때도 D가 아직 "방문 안 함"이라 또 넣는다. 큐에 들어가는 횟수가 5번에서 6번으로 는다.

이 그래프에서는 한 번 더일 뿐이지만, 여러 길이 한 점으로 모이는 격자 같은 그래프에서는 같은 점이 큐에 차수만큼 들어가 메모리와 시간이 몇 배로 는다. 넣을 때 표시하면 점마다 정확히 한 번 들어가 O(V + E)가 보장된다.

꺼내는 순서는 D, B, E, F, A, C, G이고, 거리는 D 0, B·E·F 1, A·C·G 2다.

F를 꺼낼 때 이웃 C, D, G는 이미 모두 큐에 들어갔거나 방문해 새로 넣을 것이 없다. 거리 2인 A, C, G를 꺼낼 때도 마찬가지다. 굵은 선 여섯 개(점 수 − 1)가 BFS 트리다.

14번이다. 점은 벽이 아닌 칸, 간선은 상하좌우로 맞닿은 두 칸이다. 간선 가중치가 모두 1이니 BFS가 그대로 최단 거리를 준다.

그래프를 따로 만들 필요 없이 "(r, c)의 이웃은 네 방향 중 벽이 아닌 칸"으로 그때그때 계산하는 암묵적 그래프다. 아래쪽으로 가면 G 근처(거리 8)까지 빨리 가지만 벽에 막혀 막다른 길이다. BFS는 모든 방향을 한 겹씩 넓히므로 이런 막다른 길에 속지 않는다. 게임에서 "이번 턴에 갈 수 있는 칸" 표시가 바로 이 거리 표다.

DFS는 A, B, C, F, D, E, G이고, BFS는 A, B, C, D, F, E, G다.

DFS는 B에 들어가자마자 B의 첫 이웃 C로, 다시 C의 이웃 F로 파고든다. 그래서 A에서 간선 하나 거리인 C를 세 번째에 보지만, F는 A에서 2인데 네 번째, D는 2인데 다섯 번째다. 발견 순서가 거리 순이 아니므로 DFS 트리의 길(A-B-C-F-D-E-G)은 최단 경로가 아니다. 최단 거리가 필요하면 BFS다.

A 1/12, B 2/7, D 3/6, E 4/5, C 8/11, F 9/10. 역방향 간선은 E → B이고 사이클 B → D → E → B를 알려 준다. F → E는 역방향 간선이 아니다.

E를 볼 때 스택은 A, B, D, E라 E → B는 진행 중인 조상으로 돌아가는 간선이다. 반면 F를 볼 때 E는 이미 시각 5에 완료됐다. F → E는 다른 갈래에서 끝난 점으로 건너가는 교차 간선이라 사이클이 아니다. 그래서 방향 그래프의 사이클 검사는 "방문했나"가 아니라 "스택에 걸려 있나(완료 전인가)"를 봐야 한다.

연결 요소는 3개({A, B, C}, {D, E, F, G}, {H})다. 모든 점을 글자 순으로 보며 아직 발견되지 않은 점에서 DFS를 새로 시작한 횟수가 곧 요소 수다.

한 번의 DFS는 시작점에서 닿는 점을 모두, 그리고 그것만 방문한다. 그래서 시작할 때마다 요소 하나가 통째로 칠해진다. 점과 간선을 한 번씩 보므로 전체 O(V + E)다. BFS로 해도 똑같고, 간선이 하나씩 추가되는 상황이면 다음 절의 유니온 파인드가 더 알맞다.

(가)와 (다)가 맞다. (나)와 (라)는 D가 F보다 앞서 간선 F → D를 어긴다.

간선 7개마다 "출발이 도착보다 앞인가"를 보면 된다. 위상 순서는 여러 개일 수 있다. A와 C는 서로 관계가 없어 어느 쪽이 먼저여도 되고, (다)처럼 B를 C보다 먼저 해도 된다. 정해진 것은 간선이 잇는 쌍의 앞뒤뿐이다.

A, C, B, E, D, G, F다.

처음 진입 차수가 0인 점은 A와 C다. A를 꺼내면 E는 2 → 1(C가 남음), B는 1 → 0이라 큐에 들어간다. 큐가 [C, B]라 다음은 C이고 E가 0이 된다. 이렇게 큐 순서를 따라가면 E보다 B가 먼저, G보다 D가 먼저 나온다. 큐를 우선순위 큐로 바꾸면 "가능한 것 중 글자가 가장 앞선 것"을 고르는 다른 순서(A, B, C, D, E, G, F)가 된다.

A, C, F까지만 나오고 큐가 빈다. 남은 B, D, E가 서로 물린 순환 의존(B → D → E → B)이라 "순환 의존이 있다"고 알리고 그 점들을 보여 줘야 한다.

F를 꺼내면 E의 진입 차수가 2 → 1로 줄지만 나머지 1은 사이클 안의 D에서 온다. 남은 점의 진입 차수가 모두 1 이상이면 그 점들 사이에 반드시 사이클이 있다. 여기서는 남은 점이 사이클과 정확히 같지만, 일반적으로는 사이클 뒤에 매달린 점도 함께 남으므로 정확한 고리는 DFS의 역방향 간선으로 찾아 보여 준다.

다익스트라는 A 2, T 3으로 답하지만, 참 거리는 A 1(S → B → A), T 2다.

다익스트라는 "남은 점은 지금 꺼낸 점보다 멀거나 같으니 그 점을 거쳐 돌아와도 길어질 뿐"이라는 가정에 기댄다. 음수 간선은 멀리 돌아와도 짧아질 수 있게 해 이 가정을 깬다. 틀린 A 값은 A를 거치는 T까지 번진다. 음수 간선이 있으면 벨먼-포드를 쓴다.

확정 순서는 S 0, B 2, A 5, C 9, D 10, T 13이고, T까지의 경로는 S → B → A → C → D → T다. 낡은 항목은 (7, A), (11, D), (15, T) 세 개다.

A는 처음 S에서 7로 들어가지만 B를 거치면 2 + 3 = 5라 줄어든다. D도 B에서 11로 들어갔다가 C를 거쳐 10, T도 C에서 15였다가 D를 거쳐 13이 된다. 줄어든 점마다 옛 항목이 큐에 남아 나중에 꺼낼 때 버려진다. 경로는 굵은 선(최단 경로 트리)을 T에서 거꾸로 따라가면 나온다.

간선이 가장 적은 길은 간선 3개(S → B → D → T, 무게 14 / S → A → C → T, 무게 17)이고, 가장 가벼운 길은 간선 5개인 S → B → A → C → D → T(무게 13)다.

BFS는 간선을 모두 무게 1로 보고, 다익스트라는 실제 무게를 본다. 무게 9인 B-D를 피해 가벼운 간선 여럿으로 돌아가는 편이 합이 작다. 지도로 치면 "갈아타는 횟수가 적은 길"과 "가장 빨리 도착하는 길"이 다른 것과 같다. 문제가 무엇을 최소로 하는지에 맞춰 알고리즘을 고른다.

A 5, B 2, C 4, D 3(S·T는 0). 처음 큐에 S와 T를 둘 다 거리 0으로 넣고 다익스트라를 한 번 돌리면 된다.

이는 새 점 Z를 하나 만들어 Z → S, Z → T에 무게 0인 간선을 단 뒤 Z에서 다익스트라를 돌리는 것과 같다(가상 출발점). 시간은 한 번 돌리는 O((V + E) log V) 그대로다. 소방서가 100곳이어도 마찬가지라, 100번 돌리는 것보다 훨씬 싸다. 게임의 "가장 가까운 적까지 거리" 지도도 이렇게 만든다.

1바퀴 만에 모든 거리가 확정되고, 2바퀴째에 아무것도 줄지 않아 멈춘다. 거리는 A 5, B 2, C 9, D 6으로 같다.

한 바퀴 안에서 B가 2로 준 뒤 B→A가 그 값을 바로 쓰고, A가 5로 준 뒤 A→C가 쓰는 식이다. 간선을 위상 순서로 훑으면 늘 한 바퀴면 된다. V − 1바퀴는 가장 나쁜 순서에 대비한 상한이고, "줄어든 것이 없으면 멈춤"을 두면 좋은 순서에서는 그만큼 빨리 끝난다.

1바퀴 A 5, B 6, D 13 / 2바퀴 C 8, A 2, D 10 / 3바퀴 C 5 / 4바퀴 D 7. 최종 거리는 A 2, B 6, C 5, D 7이고, 확인 바퀴에서 줄지 않아 음수 사이클은 없다.

최단 경로 S → B → A → C → D는 간선 4개다. 훑는 순서가 이 경로의 거꾸로라 바퀴마다 경로를 한 칸씩만 늘려, 간선 4개짜리 경로가 4바퀴째에야 완성됐다. D → B → A → C → D는 1 − 4 + 3 + 2 = 2로 양수인 사이클이라 문제가 없다.

불어난다. 0.9 × 160 × 0.0072 = 1.0368이라 한 바퀴에 약 3.7%가 남는다. 가중치를 −ln(환율)로 바꾸면 이 고리는 합이 -0.036인 음수 사이클이 된다.

곱이 1보다 크다는 것은 로그를 씌운 합 ln r₁ + ln r₂ + ln r₃이 0보다 크다는 것이고, 부호를 바꾸면 −ln r의 합이 0보다 작다는 것이다. 곱셈을 덧셈으로, "크다"를 "작다"로 바꿔 차익 고리 찾기가 음수 사이클 찾기가 됐다. 벨먼-포드를 V − 1바퀴 돈 뒤 한 바퀴 더 돌았을 때 줄어드는 간선이 있으면 그런 고리가 있다. 실제로는 수수료와 환율 변동 때문에 이런 고리는 아주 잠깐만 생긴다.

잘못된 순서는 2 → 1을 9로 내지만, 올바른 답은 6(2 → 3 → 4 → 1 = 3 + 1 + 2)다.

k가 안쪽이면 dist[2][1]을 단 한 번, 그 순간의 표로 정한다. 그때 dist[2][4]는 아직 직행 7이라(2 → 3 → 4 = 4는 나중 칸 계산에서 생긴다) 7 + 2 = 9가 나오고 다시는 고쳐지지 않는다. k가 바깥이면 "1~k만 거치는 최단 거리"가 k마다 표 전체에서 완성된 뒤 다음 k로 넘어가므로, 쓰는 값이 늘 그 단계에서 이미 옳다.

k=1: 4→2 = 6. k=2: 1→3 = 7, 1→4 = 11, 4→3 = 9. k=3: 1→4 = 8, 2→4 = 4. k=4: 2→1 = 6, 3→1 = 3, 3→2 = 7. 마지막 행렬은 1행 [0, 4, 7, 8], 2행 [6, 0, 3, 4], 3행 [3, 7, 0, 1], 4행 [2, 6, 9, 0]이다.