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
ํ์ด๊ฐ ๋ด ์ํ ์ฐฉ์ค์ด๋ค. ใ