๐ ๋ฌธ์
https://www.acmicpc.net/problem/4803
4803๋ฒ: ํธ๋ฆฌ
์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๊ทธ๋ํ์ ํธ๋ฆฌ๊ฐ ์๋ค๋ฉด "No trees."๋ฅผ, ํ ๊ฐ๋ผ๋ฉด "There is one tree."๋ฅผ, T๊ฐ(T > 1)๋ผ๋ฉด "A forest of T trees."๋ฅผ ํ ์คํธ ์ผ์ด์ค ๋ฒํธ์ ํจ๊ป ์ถ๋ ฅํ๋ค.
www.acmicpc.net
๐ ์์ด๋์ด

์ฌ์ดํด ์์ฑ ์์ ๊ทธ๋ํ๊ฐ ์๋๋ค.
1. BFS/ DFS๋ก ํ์
์ฐ๊ฒฐ๋ ๋ ธ๋๋ฅผ ํ์ํ๋ค, ๋ง์ฝ ๋ฐฉ๋ฌธํ๋ ๋ ธ๋๋ฅผ ์ฌ๋ฐฉ๋ฌธ ์์๋ ์ฌ์ดํด ์ด๋ฏ๋ก ํธ๋ฆฌ ๊ฐ์์์ ์ ์ธํ๋ค(-1), ๋ค๋ฅธ ๊ฒฝ์ฐ๋ ํ์ ์์ ์์ ์ ๋ ธ๋์์ (+1)
2. Union Find
์ ์ ์ด ๋ค์ด์ค๋ฉด ๋ ์ ์ ์ ๋ถ๋ชจ์ ์ ์ ์ฐพ๊ณ unionํ๋ค. ๋ง์ฝ ๋ถ๋ชจ์ ์ ์ด ๋์ผํ๋ฉด ์ฌ์ดํด์ธ ๊ฒฝ์ฐ์ด๋ค. ๋ฐ๋ผ์ ๋ถ๋ชจ์ ์ ์ด ๋์ผํ ๊ฒฝ์ฐ ์ฌ์ดํด boolean ๋ฐฐ์ด์์ ํด๋น ๋ ธ๋๋ฅผ cycle๋ก ์ฒดํฌํ์๋ค.
private static void union(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a == b) cycle[a] = true; //์ฌ์ดํด์ธ ๊ฒฝ์ฐ
else if (a < b) parents[b] = a;
else parents[a] = b;
}
ํด๋น ๊ฒฝ์ฐ ํธ๋ฆฌ์ ๊ฒฝ์ฐ์๋ ์์๋ ธ๋๊ฐ ์๊ธฐ์์ ์ด๊ณ , ์ฌ์ดํด์ด ์๋๋ผ๋ฉด ํธ๋ฆฌ์ด๋ฏ๋ก ํธ๋ฆฌ์ ๊ฐ์๋ฅผ 1 ์ฆ๊ฐ์ํจ๋ค.
//๊ทธ๋ํ ํ์
//์ฌ์ดํด
int cnt = 0;
for (int i = 0; i < n; i++) {
if (parents[i] == i && !cycle[i]) {
//๋์ ๋ถ๋ชจ๊ฐ ๋์ธ์ง(๊ทธ๋ํ์ ์์์ ๋ง ์ผ๋ค), ๊ทธ๋ํ์ ์์์ ์ด ์ฌ์ดํด์ธ ๊ฒฝ์ฐ ์ ์ธ
cnt++;
}
}
ํด๋น ์ฌํญ๊น์ง ์งํํ๋ฉด 75% ์๋ฌ ํ๋ ธ์ต๋๋ค๊ฐ ๋์จ๋ค.
์ด๋ cycle ์ด ์ ํ๋์ง ์๊ธฐ ๋๋ฌธ์ด๋ค.
| [์ถ์ฒ] https://www.acmicpc.net/board/view/107169 ๋ฐ๋ก ํ ์ผ 4 4 2 3 3 4 4 2 1 2 0 0 => Case 1: No trees. |
๊ทธ๋ํ๊ฐ ์์ฑ๋ ์ดํ์ ์์ ๋ ธ๋๊ฐ ์ฌ์ดํด์ธ ์ ์ ์ธ ์ถ๊ฐ๋๋ ๊ฒฝ์ฐ ๋ถ๋ชจ๋ ธ๋๋ ์ฌ์ดํด๋ก ์ฒดํฌํด ์ฃผ์ด์ผ ํ๋ค.
๋ฐ๋ผ์ ๋ค์๊ณผ ๊ฐ์ด ์ฌ์ดํด ์ ํ ๋ถ๋ถ์ ์ถ๊ฐํ๋ฉด
if (cycle[b] || cycle[a]) { //์ฌ์ดํด ์ ํ
cycle[a] = cycle[b] = true;
}
ํต๊ณผํ๋ค.
๋ค์์ฒ๋ผ ์ฌ์ดํด ์ ํ๋ฅผ ์์์ด ์ฌ์ดํด์ธ ๋ถ๋ชจ์๋ง ์งํํด๋ ๋๋ค(์๊ฐ์ ๋ ๊ฑธ๋ฆฐ๋ค)

private static void union(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a == b) cycle[a] = true; //์ฌ์ดํด์ธ ๊ฒฝ์ฐ
else if (a < b) {
parents[b] = a;
if (cycle[b]) cycle[a] = true;
} else {
parents[a] = b;
if (cycle[a]) cycle[b] = true;
}
}
๐ ํ์ด

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class boj_4803_ํธ๋ฆฌ {
private static int[] parents;
private static boolean[] cycle;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for (int tc = 1; ; tc++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
if (n == 0 && m == 0) break; //์ข
๋ฃ์กฐ๊ฑด
parents = new int[n];
cycle = new boolean[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
}
//๊ทธ๋ํ ์ฐ๊ฒฐ
while (m-- > 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
union(a, b);
}
//๊ทธ๋ํ ํ์
//์ฌ์ดํด
int cnt = 0;
for (int i = 0; i < n; i++) {
if (parents[i] == i && !cycle[i]) { //๋์ ๋ถ๋ชจ๊ฐ ๋์ธ์ง(๊ทธ๋ํ์ ์์์ ๋ง ์ผ๋ค), ๊ทธ๋ํ์ ์์์ ์ด ์ฌ์ดํด์ ํด๋นํ๋์ง
cnt++;
}
}
sb.append("Case ").append(tc).append(": ");
if (cnt == 0) {
sb.append("No trees.");
} else if (cnt == 1) {
sb.append("There is one tree.");
} else {
sb.append("A forest of ").append(cnt).append(" trees.");
}
sb.append("\n");
}
System.out.println(sb);
}
private static void union(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a == b) cycle[a] = true; //์ฌ์ดํด์ธ ๊ฒฝ์ฐ
else if (a < b) parents[b] = a;
else parents[a] = b;
if (cycle[b] || cycle[a]) { //์ฌ์ดํด ์ ํ
cycle[a] = cycle[b] = true;
}
}
private static int findParent(int a) {
if (a == parents[a]) return a;
return parents[a] = findParent(parents[a]);
}
}
'๋ฐฑ์ค(boj)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [JAVA]17299 ์ค๋ฑํฐ์(๊ณจ๋3, ์คํ) (0) | 2023.06.12 |
|---|---|
| [JAVA]1958 LCS3(dp, ๊ณจ๋3) (0) | 2023.06.08 |
| [JAVA]2240 ์๋๋๋ฌด, ๊ณจ๋ 5, dp (0) | 2023.06.02 |
| [JAVA]2847 ๊ฒ์์ ๋ง๋ ๋์ค์ด, ๊ทธ๋ฆฌ๋, ์ค๋ฒ4 (0) | 2023.06.01 |
| [JAVA]1063 ํน, ๊ตฌํ, ์ค๋ฒ3 (0) | 2023.05.31 |