Tarjan 알고리즘을 활용한 그래프의 연결성 분석
연결성 문제와 Tarjan 알고리즘의 역할
그래프 이론에서 우리는 다양한 연결성 문제를 다루게 된다. 방향 그래프에서는 강결합 성분(SCC)을 찾는 문제가 있으며, 무방향 그래프에서는 절단선(bridge), 절단점(cut vertex), 그리고 이들을 기반으로 한 이중 연결 성분(biconnected components) 분석이 중요하다. 이러한 문제들에 대해 Tarjan 알고리즘은 깊이 우선 탐색(DFS ...
9월 26일 15:02에 게시됨
NOIP 2024 시뮬레이션 경연 문제 분석 및 구현 가이드
철도 2 (Railway 2)
트리 구조에서 모든 노드 쌍 사이의 거리 함수 $f(i,j)$의 총합을 구하는 문제입니다. 이 문제의 핵심은 특정 노드에서 출발할 때 트리의 지름(Diameter) 끝점 중 하나로 향하는 경로가 최적의 해를 포함한다는 점입니다.
트리의 지름을 구한 뒤, 두 끝점을 기준으로 각 노드까지의 거리를 계산하여 정렬합니다. 이를 통해 각 노드별 기여도를 계산하여 ...
7월 13일 22:29에 게시됨