๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2606
- ์ ์ข ๋ฐ์ด๋ฌ์ค์ธ ์ ๋ฐ์ด๋ฌ์ค๋ ๋คํธ์ํฌ๋ฅผ ํตํด ์ ํ๋๋ค.
- ํ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํจํฐ์ ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ชจ๋ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
- ์๋ฅผ ๋ค์ด 7๋์ ์ปดํจํฐ๊ฐ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ค๊ณ ํ์. 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ์ ๋ฐ์ด๋ฌ์ค๋ 2๋ฒ๊ณผ 5๋ฒ ์ปดํจํฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒ๊ณผ 6๋ฒ ์ปดํจํฐ๊น์ง ์ ํ๋์ด 2, 3, 5, 6 ๋ค ๋์ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค. ํ์ง๋ง 4๋ฒ๊ณผ 7๋ฒ ์ปดํจํฐ๋ 1๋ฒ ์ปดํจํฐ์ ๋คํธ์ํฌ์์์ ์ฐ๊ฒฐ๋์ด ์์ง ์๊ธฐ ๋๋ฌธ์ ์ํฅ์ ๋ฐ์ง ์๋๋ค.
- ์ด๋ ๋ 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ๋ค. ์ปดํจํฐ์ ์์ ๋คํธ์ํฌ ์์์ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์๋ ์ปดํจํฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค.
- ์ปดํจํฐ์ ์๋ 100 ์ดํ์ธ ์์ ์ ์์ด๊ณ ๊ฐ ์ปดํจํฐ์๋ 1๋ฒ ๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฒํธ๊ฐ ๋งค๊ฒจ์ง๋ค.
- ๋์งธ ์ค์๋ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ ์์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ด์ด์ ๊ทธ ์๋งํผ ํ ์ค์ ํ ์์ฉ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ์ ๋ฒํธ ์์ด ์ฃผ์ด์ง๋ค.
- 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ์ ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- HashSet ๋ฐฐ์ด์ ๋ง๋ค์ด์ ๊ทธ ๋ฐฐ์ด์ ์ปดํจํฐ ์ฐ๊ฒฐ์ ๋ณด๋ฅผ ์ ์ฅํ๋ค. (HashSet์ ์ฌ์ฉํ๋ ์ด์ ๋ ์ปดํจํฐ ๋ฒํธ๋ฅผ ์ค๋ณต ์ ์ฅํ์ง ์๊ธฐ ์ํด์์ด๋ค.)
- ๊ทธ๋ฆฌ๊ณ N+1 ํฌ๊ธฐ์ boolean ๋ฐฐ์ด์ ๋ง๋ค์ด์ ๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ์ฒดํฌํ๋ค.
- ์ฐ์ ์ปดํจํฐ๊ฐ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ ๋ณด๋ฅผ ์ ๋ ฅ๋ฐ์ ๋, [a]๋ฐฐ์ด์ b๋ฅผ ์ ์ฅํ๊ณ [b]๋ฐฐ์ด์ a๋ฅผ ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ BFS๋ฅผ ๋๋ฆฐ๋ค.
- Queue์ ์ฒ์์ ์ฐพ์ ์ปดํจํฐ ๋ฒํธ๋ฅผ ๋ฃ๊ณ ํด๋น ๋ฒํธ๋ฅผ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ๋ฅผ ํ๋ค.
- ๊ทธ๋ฆฌ๊ณ while๋ฌธ์ Queue๊ฐ ๋น์ด์ง๋๊น์ง ๋๋ฉด์ Queue์์ ๋งจ ์์ ๊ฐ์ ๋นผ๊ณ ํด๋น ๊ฐ์ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ๋ ArrayList์ ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ํด๋น ๋ฒํธ์ ์ฐ๊ฒฐ๋์ด์๋ ์ปดํจํฐ ๋ฒํธ๋ค ์ค ๋ฐฉ๋ฌธํ์ง ์์ ๋ฒํธ๊ฐ ์๋ค๋ฉด, ํด๋น ๋ฒํธ๋ฅผ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๊ณ Queue์ ๊ทธ ๋ฒํธ๋ฅผ ๋ฃ๋๋ค.
- ๊ณ์ ๋ฐ๋ณตํ๋ค๋ณด๋ฉด ์ฒ์์ ์ฐพ์ ์ปดํจํฐ ๋ฒํธ์ ์ฐ๊ฒฐ๋ ๋ฒํธ๋ค์ด Queue์ ๋ค์ด๊ฐ๋ค๊ฐ ๋์ค๋ฉด์ ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ๋ ArrayList์ ์ ์ฅ๋๋ค.
- ๊ทธ๋ฆฌ๊ณ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ ๋, ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ๋ ArrayList์์ 1์ ๋นผ๊ณ ์ถ๋ ฅํ๋ค. (ํด๋น ArrayList์ ์ด๊ธฐ ์ปดํจํฐ ๋ฒํธ๋ ์ ์ฅ์ด ๋์ด์์ผ๋ฏ๋ก, ๋ณธ์ธ ๋ฒํธ๋ ๋นผ์ผ๋๊ธฐ ๋๋ฌธ)
๊ฒช์ ์ํ์ฐฉ์ค
- ์ค๋๋ง์ BFS๋ฅผ ์จ์ ์กฐ๊ธ ์๊ฐ์ด ๊ฑธ๋ ธ๋ ๊ฒ ๊ฐ๋ค.... (์์ผ๋ก ๋์ฌ ๊ทธ๋ํ ๋ฌธ์ ๋ค... ๊ธด์ฅ๋๋ค... ใ ใ )
์ฝ๋
import java.util.*;
import java.io.*;
public class BOJ2606 {
static Set<Integer> worm[];
static Set<Integer> result;
static boolean visited[];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// ์ปดํจํฐ ๊ฐ์
int N = Integer.parseInt(br.readLine());
// ์ปดํจํฐ ์์ ์
int C = Integer.parseInt(br.readLine());
// ์ปดํจํฐ ์ฐ๊ฒฐ ์ ์ฅํ HashSet ๋ฐฐ์ด
worm = new HashSet[N + 1];
// HashSet์ผ๋ก ์ด๊ธฐํ
for (int i = 0; i <= N; i++) {
worm[i] = new HashSet<>();
}
// ๊ฒฐ๊ณผ ์ปดํจํฐ๋ฅผ ์ ์ฅํ set (์ค๋ณต ๊ฐ์ด ๋ค์ด๊ฐ๋ฉด ์๋๋ฏ๋ก)
result = new HashSet<>();
// ๋ฐฉ๋ฌธ ์ฌ๋ถ
visited = new boolean[N + 1];
for(int i = 0; i < C; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
// ์ปดํจํฐ ๋ฒํธ ์
๋ ฅ
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// ํด๋น ์ปดํจํฐ์ ์๋ฐฉํฅ์ผ๋ก ์ฐ๊ฒฐ
worm[a].add(b);
worm[b].add(a);
}
BFS(1);
// ํด๋น ๊ฒฐ๊ณผ ArrayList์ ๋ณธ์ธ ๋ฒํธ๋ ํฌํจ๋์ด ์์ผ๋ฏ๋ก 1์ ๋บ
System.out.println(result.size() - 1);
}
public static void BFS(int c){
Queue<Integer> q = new LinkedList<>();
// queue์ ์ฐพ์ ์ปดํจํฐ ๋ฒํธ๋ฅผ ๋ฃ์ด์ค
q.offer(c);
// ํด๋น ๋ฒํธ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
visited[c] = true;
// queue๊ฐ ๋น๋๊น์ง ๋ฐ๋ณต
while(!q.isEmpty()){
// queue์ ๋ค์ด์๋ ๋ฒํธ๋ฅผ ๊บผ๋
int num = q.poll();
// ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ ๋ฐฐ์ด์ ํด๋น ๋ฒํธ ์ ์ฅ
result.add(num);
// ํด๋น ๋ฒํธ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋ ์ปดํจํฐ ๋ฒํธ๋ค ์ค
for(int i : worm[num]){
// ๋ฐฉ๋ฌธํ์ง ์์ ๊ณณ์ด ์๋ค๋ฉด
if(!visited[i]){
// ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ ํ
visited[i] = true;
// queue์ ํด๋น ๋ฒํธ๋ฅผ ๋ฃ์
q.offer(i);
}
}
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 9375 ํจ์ ์ ์ ํด๋น (0) | 2024.07.28 |
---|---|
[Java] BOJ 9095 1, 2, 3 ๋ํ๊ธฐ (0) | 2024.07.28 |
[Java] BOJ 2579 ๊ณ๋จ ์ค๋ฅด๊ธฐ (0) | 2024.07.27 |
[Java] BOJ 1463 1๋ก ๋ง๋ค๊ธฐ (2) | 2024.07.27 |
[Java] BOJ 1003 ํผ๋ณด๋์น ํจ์ (0) | 2024.07.26 |