ํฐ์คํ ๋ฆฌ ๋ทฐ
https://www.acmicpc.net/problem/11724
์ดํด
๋ฌธ์ ํ์ด์ ์์ ๋ฌธ์ ๋ฅผ ์ดํดํด๋ณด์.
- ์ฐ๊ฒฐ ์์(Connected Component)๋ ์ฐ๊ฒฐ๋ ์ ์ ์ ์งํฉ์ ์๋ฏธํ๋ค. ๋ค์ ์ด๋ฏธ์ง์์์ ์ฐ๊ฒฐ ์์๋ 4๊ฐ์ด๋ค.
- ๋ฐ๋ผ์ ํด๋น ๋ฌธ์ ๋ ๊ทธ๋ํ ํ์์ ํตํด ์ฐ๊ฒฐ๋ ์ ์ ์ ๋ชจ๋ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๊ณ
- ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ๋์ง ์์ ์ ์ ์ด ๋ฐ๊ฒฌ๋๋ฉด ์๋ก์ด ์ฐ๊ฒฐ ์์์์ ์๋ฏธํ๋ค.
ํ์ด
- ์ ์ฒด ๋ ธ๋(1~N)๋ฅผ ์ํํ๋ฉฐ ํด๋น ๋ ธ๋๊ฐ ๋ฐฉ๋ฌธ๋์ง ์์๋ค๋ฉด, ์ฐ๊ฒฐ ์์(result)๋ฅผ ์นด์ดํธํ๋ค.
- ํด๋น ๋ ธ๋๋ฅผ ์์์ผ๋ก ๊ทธ๋ํ ํ์(BFS or DFS)์ ์งํํ๋ฉฐ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๋ค.(์ด ๊ธ์์ BFS๋ฅผ ๊ตฌํํ๋ค)
- ์ฃผ์* ์ฐ๊ฒฐ๋ ๋ ธ๋๋ฅผ ๋ฐ๊ฒฌ๊ณผ ๋์์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ์ง ์์ผ๋ฉด ๋ฌดํ๋ฃจํ์ ๋น ์ง ์ ์์ผ๋ ์ฃผ์ํ์.
์ฝ๋
package BOJ;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class ์ฐ๊ฒฐ_์์์_๊ฐ์_11724 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] input = br.readLine().split(" ");
final int N = Integer.parseInt(input[0]);
final int M = Integer.parseInt(input[1]);
boolean[] visited = new boolean[N + 1];
int result = 0;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
String[] connectInfo = br.readLine().split(" ");
int u = Integer.parseInt(connectInfo[0]);
int v = Integer.parseInt(connectInfo[1]);
graph.get(u).add(v);
graph.get(v).add(u);
}
for (int i = 1; i <= N; i++) {
if (visited[i]) {
continue;
}
result += 1;
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
while (!queue.isEmpty()) {
Integer current = queue.poll();
visited[current] = true;
for (Integer node : graph.get(current)) {
if (!visited[node]) {
visited[node] = true;
queue.add(node);
}
}
}
}
bw.write(Integer.toString(result));
bw.close();
br.close();
}
}
๋ฐ์ํ
'PS > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 7576 : ํ ๋งํ - java [์๋ฐ] (0) | 2022.03.02 |
---|---|
[๋ฐฑ์ค] 2667 : ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ - java [์๋ฐ] (0) | 2022.02.28 |
[๋ฐฑ์ค] 2252 : ์ค ์ธ์ฐ๊ธฐ - java [์๋ฐ] (0) | 2022.02.27 |
[๋ฐฑ์ค] 2805 : ๋๋ฌด ์๋ฅด๊ธฐ - java [์๋ฐ] (0) | 2022.02.26 |
๊ณต์ง์ฌํญ
์ต๊ทผ์ ์ฌ๋ผ์จ ๊ธ
์ต๊ทผ์ ๋ฌ๋ฆฐ ๋๊ธ
- Total
- Today
- Yesterday
TAG
- Aws Reinvent 2023
- mysql
- ๊น์ด/๋๋น ์ฐ์ ํ์(DFS/BFS)
- ์ฝ๋ฉํ ์คํธ
- ์ฅ์ ํ๊ณ
- ํธ๋์ญ์ ๊ฒฉ๋ฆฌ ์์ค
- kotlin s3 upload
- 2023 ๊ฐ๋ฐ์ ํ๊ณ
- ํด์
- ์ถ์ ์ง๋
- 2๋ ์ฐจ ์๋ฒ ๊ฐ๋ฐ์
- ๋ฑ ํฌ์๋ฌ๋ ๊ฐ๋ฐ์
- ์ข์ ๊ฐ๋ฐ์
- ๋ฐฑ์ค
- ์ข์ ์ฝ๋๋ ๋ฌด์์ธ๊ฐ?
- mysql ์คํ ๊ณํ
- ์๊ณ ๋ฆฌ์ฆ
- Go
- AWS re:Invent 2023
- ์ข์ ์์ง๋์ด
- grpc client
- 2023 ํ๊ณ
- Golang
- ํ(Heap)
- ์คํ/ํ
- ํ๋ก๊ทธ๋๋จธ์ค
- golang oomkilled
- rate limit
- HTTP
- ์ข์ ๊ฐ๋ฐ์ ๋๊ธฐ
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
๊ธ ๋ณด๊ดํจ