23324번: 어려운 모든 정점 쌍 최단 거리
첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다. 다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$
www.acmicpc.net
유니온 파인드로 접근하였다.
풀이
문제의 핵심은 가중치가 주어지는 간선은 오로지 한 개라는 것. 즉 가중치가 있는 간선을 거쳐가는 경로의 개수를 찾는 문제다. 가중치가 없는 간선들을 먼저 연결해 준 뒤 마지막으로 가중치가 존재하는 간선을 연결할 때, 연결하려는 두 컴포넌트의 개수를 서로 곱해주면 해당 간선을 거쳐가는 간선의 개수를 구할 수 있게 된다. 예제를 기준으로 그림으로 설명하면 다음과 같다.
2번 정점과 3번 정점을 연결할 때, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5의 경로에서 2-3 간선을 이용해야만 한다. 즉 2번 정점이 속한 컴포넌트의 정점개수와 3번 정점이 속한 컴포넌트의 정점 개수를 서로 곱해주면 정답이다.
단, 예제입력 2와 같이 가중치가 존재하는 간선을 연결할 때 이미 두 정점이 같은 컴포넌트인 경우 비용 0인 간선으로 우회가 가능하기에 이때는 정답이 0이다.
따라서 유니온 파인드 알고리즘을 통해 각 컴포넌트의 개수를 핸들링하여 정답을 출력해 주면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [15559] 내 선물을 받아줘 (0) | 2023.10.31 |
|---|---|
| [1765] 닭싸움 팀 정하기 (0) | 2023.10.30 |
| [23743] 방탈출 (0) | 2023.10.01 |
| [1833] 고속도로 설계하기 (0) | 2023.09.30 |
| [16926] 배열 돌리기 1 (0) | 2023.06.15 |