Hyun's_Devlog

유니온 파인드로 접근하였다.

풀이

문제의 핵심은 가중치가 주어지는 간선은 오로지 한 개라는 것. 즉 가중치가 있는 간선을 거쳐가는 경로의 개수를 찾는 문제다. 가중치가 없는 간선들을 먼저 연결해 준 뒤 마지막으로 가중치가 존재하는 간선을 연결할 때, 연결하려는 두 컴포넌트의 개수를 서로 곱해주면 해당 간선을 거쳐가는 간선의 개수를 구할 수 있게 된다. 예제를 기준으로 그림으로 설명하면 다음과 같다.

2번 정점과 3번 정점을 연결할 때, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5의 경로에서 2-3 간선을 이용해야만 한다. 즉 2번 정점이 속한 컴포넌트의 정점개수와 3번 정점이 속한 컴포넌트의 정점 개수를 서로 곱해주면 정답이다.

단, 예제입력 2와 같이 가중치가 존재하는 간선을 연결할 때 이미 두 정점이 같은 컴포넌트인 경우 비용 0인 간선으로 우회가 가능하기에 이때는 정답이 0이다.

따라서 유니온 파인드 알고리즘을 통해 각 컴포넌트의 개수를 핸들링하여 정답을 출력해 주면 된다.

정답 코드

https://www.acmicpc.net/problem/10216

기하학이 한 방울 들어간 유니온 파인드 문제. 이전에 풀다가 포기했던 문제다. 거리 계산 부분에서 아무 생각 없이 2차원 배열로서의 거리로 접근했는데, 옳은 방법이 아니었다. 2차원 배열 없이 풀 수 있는 문제.

풀이

입력되는 좌표와 범위를 입력받을 때마다, 모아놓은 나머지 지점들과의 거리를 계산, 범위가 겹치는 경우 유니온을 수행하여 마지막에 그룹의 개수를 출력하면 된다.
이번에는 그룹의 노드 개수를 파악하는 문제는 아니므로, 합병 수행 시 루트의 값은 바꾸지 않고 자식으로 들어갈 노드의 번호만 루트의 번호로 바꾸어 주면 된다.
두 지점의 범위 판정은 간단하다. 두 원점 사이의 거리가 두 지점의 범위의 총합보다 같거나 짧은 경우, 범위가 겹치는 것으로 판단하면 된다.

정답 코드