1. 문제에 대하여 📦
https://www.acmicpc.net/problem/4803
(1) 조건 분석 📊
- 트리의 수 세기
- 사이클이 있는 그래프는 트리가 아니므로, 갯수 센 것에서 제외하기
2. 코드가 나오기까지 🛠️
KEY WORD: Union & Find
나머지 정점 N개 간선 N-1 개 등, 다른 트리의 특징들은 해당 문제에서 2개의 정점 사이에는 하나의 간선밖에 업다고 못 박아 두었기 때문에 신경 쓸 필요가 없다. 따라서 사이클이 생기는지만 신경써서 확인해주면 된다.
필자는 다음과 같은 방법을 거쳐 사이클 여부를 확인했다. (내용을 진행하기 앞서, 독자들이 Union&Find에 대해 알고 있다는 가정 하에 설명을 이어가겠다. 혹시 모르시는 분은 [알고리즘] 유니온 파인드 쉽게 이해하기 ^^를 한 번 읽어오시길 바란다.)
A. 사이클이 있는지 확인하는 방법
- 간선 리스트를 하나씩 순회하며 두 정점 사이를 잇는다.
- 두 정점의 조상을 봤는데, 서로 다르다. -> 번호가 작은 쪽을 조상으로 두 집합을 합한다.
- 이미 둘의 조상이 같다? -> '이번 간선을 이으면 해당 노드를 가진 집합은 사이클을 이룬다.' 는 소리이다.
왜 그런가?
이유는 다음과 같다.
두 정점 사이의 간선은 오로지 하나이다. 따라서 이미 둘이 같은 조상을 가진다는 것은 간접적으로 서로 이어져 있다는 것인데, 이번에 직접적으로 잇게 되니 당연히 사이클이 발생한다.
B. 특정 노드가 사이클의 구성원인지 확인하는 방법 (Wrong)
만약 위에서 사이클을 완성시켰던 정점인 B와 A 그리고 그 부모들만 사이클이라고 체크해놓고 개수 세기에서 제외시킨다면 다음과 같은 오류가 발생한다. 원래 있던 집합이 {A,C,E}, {D,E,Z} 이고 이번에 간선 A->B가 들어왔다고 하자.
그럼 find 함수에 A 또는 B를 넣어서 그들의 부모를 찾을 것이기 때문에 C,D,E는 사이클의 구성원으로 확인이 되겠지만, Z의 경우 확인할 수가 없다. 이걸 해결 할 수 있는 방법은 다음과 같다.
C. 특정 노드가 사이클의 구성원인지 확인하는 방법 (Right)
필자가 사이클 여부를 확인한 방법은 다음과 같다.
- 유니온 연산할 때마다 각 자식 노드에 대하여
경로 압축을 진행한다.
그러면 다음과 같이 문어발 형태가 될 것이다.
- 이후 만약 해당 문어발 중 하나라도 사이클이 생기면, 루트와 연결된 모든 자식 노드는
사이클의 구성원이다. 이미 경로 압축을 통해 모든 자식노드가 루트노드를 바라보게 했음으로, 부모 배열에서 부모가 해당 루트 노드인 경우를 찾아서 사이클의 구성원임을 체크한다.
만약 B와 C 사이에 사이클이 생겼다고 다면 이후 거리 배열의 부모가 B,C의 부모와 같은 A인 녀석들을 확인한다.
그림이 조약해서 죄송하지만 위를 index, 밑을 value라고 보고, 아까의 A~Z까지를 차례대로 1,2,3,4 라고 보자. 우리는 경로 압축을 통해 모든 노드가 자신의 루트 노드를 보고 있음을 보장했으므로, 해당 거리 배열을 순회 하면 된다.
(1) 시간복잡도 분석 ⏳
- 경로압축을 한 find의 연산 시간: O(a(N)) = 상수 시간
- 당연히 그럼 union 또한 해당 find를 두 번 한 수임으로 상수 시간이다.
- 사이클이 생길 때마다 거리배열 전체를 순회한다. 따라서 최악의 경우 O(NM)의 시간복잡도가 든다ㅏ. 배열의 크기는 50, 간선의 개수는 <=2500 이다. 따라서 최대 125000 의 연산 시간이 든다.
3. 코드 🌐
(1) SUDO CODE 💬
+ 0. TC마다 값 초기화 받기, 사이클의 구성원이냐? boolean 배열을 isCycle이라 지칭하겠다.
+ 1. 매 간선 확인 후 UNION(정점 one, 정점 another) 진행
+ 2. 이미 서로 조상이 같으면 이번 간선으로 사이클이 생긴다는 의미
- (1) 거리 배열 순회
- (2) 이번에 확인한 두 정점과 루트노드가 같은 것들 모두 isCycle[i] = true로 전환(2) JAVA CODE ☕
import java.io.*;
import java.util.*;
public class Main{
static int N, M;
static int [] dist;
static int [] flag; // 0 = no visited, 1 = visited, 2 = invalid;
public static void main(String[] args) throws IOException {
int tc = 0;
// System.setIn(new FileInputStream("src/testcase/tc4803.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
tc++;
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if(N == 0 && M == 0) break;
dist = new int [N+1];
flag = new int [N+1];
for(int i = 0; i < N+1; i++){
dist[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
union(a,b);
}
int cnt = 0;
for (int i = N; i > 0; i--) {
if(flag[i] == 0) {
int ancestor = find(i);
if(flag[ancestor] == 0) {
cnt++;
flag[ancestor] = 1;
}
}
}
switch (cnt) {
case 0:
System.out.println("Case "+tc+": No trees.");
break;
case 1:
System.out.println("Case "+tc+": There is one tree.");
break;
default:
System.out.println("Case "+tc+": A forest of "+ cnt + " trees.");
}
}
}
public static void union(int a, int b) {
int ancestorA = find(a);
int ancestorB = find(b);
if(ancestorA == ancestorB || flag[ancestorA] == 2 || flag[ancestorB] == 2) {
checkInvalid(ancestorA);
checkInvalid(ancestorB);
}else if(ancestorA < ancestorB){
dist[ancestorB] = ancestorA;
}else {
dist[ancestorA] = ancestorB;
}
}
public static int find(int i){
if(dist[i] == i) return i;
dist[i] = find(dist[i]);
return dist[i];
}
public static void checkInvalid(int ancestor){
for (int i = 1; i < N+1; i++) {
if(find(i) == ancestor) flag[i] = 2;
}
}
}4. 트러블 슈팅 or 배운 점 📝
위에 나온 Wrong 풀이가 내 시행 착오이다. ㅠ
