01-09 18:44
Recent Posts
Recent Comments
Tags
- ICT๋ฉํ ๋ง
- ํ๋ก๋ณด๋ ธ
- ์๋ฐ
- ์ด๋ธ์
- mysql
- ์จ์ผ๋ํ
- RaspberryPi
- API MarketPlace ๊ธ๋ก๋ฒ ์ํฌํฐ์ฆ
- ํ์ด์๊ณต๋ชจ์
- ์คํฝ์ค๋น
- DATABASE
- ํ์ด์ฌ
- linux
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- Spring
- TSQL
- ์๋์ด๋ ธ
- ICT
- ict๊ณต๋ชจ์
- ์คํฝ๋ ํ
- ํ์ด์
- API๋ง์ผํ๋ ์ด์ค
- JOBํ๊ณ
- ์กํ๊ณ
- Naver Cloud
- DB
- SQL
- Java
- python
- appetizer
- Today
- Total
miinsun
[BAEKJOON] ๋ฐฑ์ค ๊ทธ๋ํ 11724 :: ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ณธ๋ฌธ
Algorithm/Baekjoon
[BAEKJOON] ๋ฐฑ์ค ๊ทธ๋ํ 11724 :: ์ฐ๊ฒฐ ์์์ ๊ฐ์
miinsun 2022. 3. 29. 23:23
๐ฌ ๋ฌธ์ ์ค๋ช
๋ฐฉํฅ ์๋ ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ก์ ๋, ์ฐ๊ฒฐ ์์ (Connected Component)์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐จ ์ ์ถ๋ ฅ ์
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N๊ณผ ๊ฐ์ ์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
- ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฐ์ ์ ์ ๋์ u์ v๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ u, v ≤ N, u ≠ v)
- ๊ฐ์ ๊ฐ์ ์ ํ ๋ฒ๋ง ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ์ฐ๊ฒฐ ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1)
6 5
1 2
2 5
5 1
3 4
4 6
์์ ์ถ๋ ฅ 1)
2
์์ ์ ๋ ฅ 2)
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3
์์ ์ถ๋ ฅ 2)
1
โ
โ
๐ป Main.java
- ์ด์ ๊ฒ์๊ธ 'DFS์ BFS' ๋ฌธ์ ๋ฅผ ๋ฒ ์ด์ค๋ก ํด๊ฒฐ
- check๋ฐฐ์ด์ ์ด๋ฒ ๋ฐฉ๋ฌธ์ด ๋ช๋ฒ์งธ ๋ฐฉ๋ฌธ์ธ์ง ์นด์ดํ ํด์ค๋ค.
- ์ฐ๊ฒฐ ์์๋ ์๋์ ๊ฐ์ ์ด๋ฏธ์ง๋ค.
/* ๋ฐฑ์ค ๊ทธ๋ํ - 11724 :: ์ฐ๊ฒฐ ์์์ ๊ฐ์ */
import java.util.*;
import java.io.*;
public class Main {
public void DFS(int n, int s, boolean[][] arr, int[] check, int order) {
//์ฒดํฌ๊ฐ ์๋์์ ๊ฒฝ์ฐ์๋ง order๋ฅผ ๋ด์์ค๋ค.
if(check[s] == 0)
check[s] = order;
for(int i = 1; i <= n; i++) {
if (check[i] == 0) {
if(arr[s][i]) {
DFS(n, i, arr, check, order);
}
}
}
}
public static void main(String[] args) throws IOException{
Main main = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
boolean[][] arr = new boolean [n + 1][n + 1];
int[] check = new int [n + 1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// ๋ฐฉํฅ ์๋ ๊ทธ๋ํ๋
// (x,y) (y,x) ์ขํ๋ฅผ ๋ชจ๋ ์ ์ฅํด์ค๋ค.
arr[x][y] = true;
arr[y][x] = true;
}
// DFS
int order = 1;
for(int i = 1; i <= n; i++) {
// ๋ฐฉ๋ฌธํ ์ ์ด ์์ ๊ฒฝ์ฐ์๋ง
// ์ ์ ์ ๋ฐฉ๋ฌธํ๋ค.
if(check[i] == 0) {
main.DFS(n, i, arr, check, order);
order++;
}
}
// check๋ฐฐ์ด์์ ๊ฐ์ฅ ํฐ ๊ฐ์ด ์ฐ๊ฒฐ์์์ ๊ฐ์ด๋ค.
int answer = 0;
for(int i : check)
answer = Math.max(i, answer);
System.out.println(answer);
br.close();
}
}
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BAEKJOON] ๋ฐฑ์ค ๊ทธ๋ํ 2331 :: ๋ฐ๋ณต์์ด (0) | 2022.03.31 |
---|---|
[BAEKJOON] ๋ฐฑ์ค ๊ทธ๋ํ10451 :: ์์ด ์ฌ์ดํด (0) | 2022.03.30 |
[BAEKJOON] ๋ฐฑ์ค ๊ทธ๋ํ 1260 :: DFS์ BFS (0) | 2022.03.28 |
[BAEKJOON] ๋ฐฑ์ค ๊ธฐ์ด ์ํ 9613 :: GCD ํฉ (0) | 2022.03.28 |
[BAEKJOON] ๋ฐฑ์ค ๊ธฐ์ด ์ํ 1850 :: ์ต๋๊ณต์ฝ์ (0) | 2022.03.27 |
Comments