"기초 트랙에서 구조와 비용이 세상을 보는 렌즈라고 했지. 여기 그 렌즈의 가장 날카로운 버전이 있어. 무언가를 '것들, 그리고 그것들이 어떻게 관계 맺는가'로 묘사하는 순간, 이미 그래프를 그린 거야."
날카로워진 렌즈
그래프는 간선이라는 관계로 이어진 정점, 그러니까 것들이야. 정의는 여기서 끝인데, 허무할 만큼 일반적이라는 게 정확히 그 힘이야. 중요한 시스템은 거의 다 뜯어보면 그래프거든.
- 지도는 교차로가 정점이고 도로가 간선이야. 지금 이 순간에도 GPS가 그래프 알고리즘을 돌리고 있어.
- 소셜 네트워크는 사람이 정점이고 친구 관계가 간선이야. '알 수도 있는 사람'이 바로 그래프 질의고.
- 웹은 페이지가 정점이고 하이퍼링크가 간선이야. Google의 원조 PageRank가 그 그래프에 순위를 매긴 거였어.
- 의존성은 패키지, 빌드 단계, 강의 선수과목처럼 다른 것보다 먼저 와야 하는 정점들이야. 모든 패키지 매니저가 그래프 문제를 푸는 셈이지.
- 뇌, 분자, 공급망, 인용 관계, 인터넷 그 자체도 전부 그래프고.
첫 트랙에서 잡은 그 세계관이 여기서 제 힘을 다 드러내는 거야. 관계는 현실의 근본 성질이고, 그래프가 바로 그 자료구조니까.
지금까지 배운 게 전부 특수한 그래프였어
앞선 트랙들의 구조를 그래프 관점에서 다시 볼 수 있어. 트리는 연결돼 있고 사이클이 없는 그래프고, 연결 리스트는 각 노드가 많아야 다음 노드 하나를 가리키는 경로 모양의 방향 그래프야. 마지막 노드에는 다음이 없고 원형 리스트는 사이클이니까, 그냥 "모든 노드가 자식을 하나 갖는 트리"라고 부르면 틀려. 어떤 제약이 걸려 있는지 분명히 해야 일반 그래프와의 관계가 선명해져.
간선의 어휘
그래프 문제의 성격을 결정하는 중요한 구분이 둘 있어. 방향이 있느냐 없느냐, 그리고 가중치가 있느냐 없느냐. 가중치 없는 최단 경로에는 BFS가 맞고, 가중치가 있는 최단 경로는 가중치 조건까지 봐야 해. 모든 가중치가 0 이상이면 Dijkstra를 쓸 수 있지만, 음수 가중치가 섞여 있으면 Bellman-Ford 같은 다른 도구가 필요하거든. "가중치가 있으면 Dijkstra"로 곧장 건너뛰지 마.
그래프는 정점(것들)과 간선(관계)으로 이뤄진, 존재하는 가장 일반적인 구조야. 트리와 리스트는 거기서 규칙을 덜어낸 형태고. 어떤 문제를 '것들이 있고 그것들이 어떻게 이어지는가'로 표현할 수 있다면 그건 그래프 문제야. 세계관 렌즈가 온전히 힘을 발휘하는 지점이지.
피파의 고백
아빠는 'X를 어떻게 모델링해?'라는 질문에 '것들이 뭐고, 어떻게 관계 맺어?'로 답하는 습관이 있어. 한동안은 그냥 말버릇이라고 생각했지. 그러다 그 질문이 추천, 스케줄링, 라우팅, 의존성 해결처럼 제각각으로 보이던 문제를 같은 문제로 바꿔놓는다는 걸 알아챘어. 그래프에 순회 하나를 얹으면 되는 문제로 말이야. 기초 트랙에서 배운 렌즈가 그때부터 슬로건이 아니라 내가 실제로 두는 첫 수가 됐어. 정점에 이름을 붙이고 간선에 이름을 붙이고 나면, 막막하던 게 BFS냐 DFS냐를 고르는 문제로 바뀌거든.