소스코드 : github.com/CaChiJ/JustCodes/blob/main/Algorithm%20Solutions/Tree/BOJ1045.cpp
🔎 살펴보기
우선 문제 설명을 보자.
0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, 튜플 (A, B) < (C, D)이면 x > y, 즉 x의 우선순위가 더 높다. 여기서 ai ≠ bi인 가장 작은 양의 정수 i에 대해 ai < bi이면 (a1, ..., ak) < (b1, ..., bk)로 정의한다.
도로의 집합은 하나 이상의 도로가 우선순위에 대한 내림차순으로 정렬되어 있는 것이다. 집합 사이에도 우선순위가 있는데, 두 집합을 튜플로 나타냈을 때의 우선순위를 따른다. 한 집합에 있는 도로만으로 임의의 도시에서 임의의 도시로 이동할 수 있을 때, 그 집합은 연결되어 있다고 한다.
M개의 도로를 가진 도로의 집합 중 연결되어 있으면서 우선 순위가 가장 높은 것을 찾아라.
요약하자면 다음과 같다.
A와 B(A < B)를 양 끝점으로 하는 도로를 튜플 (A, B)로 나타내자. 두 도로를 비교할 때 튜플이 작은쪽의 우선순위가 더 높다. 가장 높은 우선순위를 가지며 모든 도시를 연결하는 도로 M개의 집합을 구하여라.
여기서 핵심은 1. 모든 도시를 연결 2. 가장 높은 우선순위이다. 1은 Union-Find를 이용해 찾을 수 있다. 모든 도시가 연결된 후에 남는 도로 중 우선순위가 높은 도로들을 집합에 추가하면 문제를 해결할 수 있을 것이다.
📜 로직
이 글에서는 필자가 작성한 코드를 토대로 로직을 설명하겠다. 물론 더 간단한 방법이 있을 수 있다.
1. 도시 연결하기
인접 행렬의 행 인덱스를 i, 열 인덱스를 j라고 하자. 도시 i에서 도시 j로 가는 도로가 있다면 도시 j에서 도시 i로 가는 도로도 존재한다. 도로의 중복 입력을 막기 위해 j < i일 때의 입력은 버린다. 이렇게 거르면 먼저 입력되는 도로가 뒤에 입력되는 도로보다 우선순위가 높다는 사실을 알 수 있다. 따라서 도시가 입력될 때마다 다음을 수행한다.
if ( i와 j가 연결되어 있지 않음 ) { i와 j를 unite한다 }
else { (i, j)를 저장해둔다 }
입력이 끝나고 난 뒤 모든 도시의 루트가 같은지 검사하면 모든 도시가 연결되었는지 알 수 있다.
이렇듯 입력의 특성을 그리디하게 이용하면 우선순위 큐를 이용하지 않아도 되므로 시간복잡도가 작아진다.
2. 도로 M개 만들기
위에서 i와 j가 이미 연결되어 있을 때 (i, j)를 저장해두라고 했다. 순서대로 잘 저장해 두었다면 앞에서부터 M-N+1개를 뽑아 집합에 추가하면 된다.
3. 각 도시를 끝점으로 갖는 도로 개수 구하기
크기 N의 배열을 0으로 초기화해두고 위 1과 2에서 도로를 뽑을 때마다 각 도로를 인덱스로 접근하여 1을 더해주면 된다.
⏱ 시간복잡도
이 알고리즘은 입력의 크기 과 union-find의 시간 복잡도 에 지배되므로 시간 복잡도는 이다.
🌱 개선점
로직에서 2번을 1번에 합칠 수 있다. 끝점으로 하는 두 도시가 이미 연결되어 있음에도 집합에 추가하는 경우는 총 M-N+1번 일어난다. 이 경우가 일어날 때마다 카운트하면서 M-N+1번만 일어나도록 제한해주면 된다. 복잡도에는 영향을 주지 않지만 속도와 메모리 성능 모두 개선된다.
