👀 문제
https://www.acmicpc.net/problem/11724
👊 도전
1. 설계
- 연결 요소는 그래프의 개수와 같다. 따라서 DFS로 그래프 탐색 후 개별 그래프의 갯수를 구하면 된다.
2. 구현 (성공 코드)
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
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int n, m;
static int[][] array;
static boolean[] visit;
public static void dfs(int idx) {
for(int i=1;i<=n;i++) {
if(visit[i]) continue;
if(array[idx][i]==1) {
visit[i]=true;
dfs(i);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
array=new int[n+1][n+1];
visit=new boolean[n+1];
for(int i=0;i<m;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
array[a][b]=1;
array[b][a]=1;
}
int cnt=0;
for(int i=1;i<=n;i++) {
if(visit[i]) continue;
cnt++;
dfs(i);
}
System.out.println(cnt);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DFS를 이용한다
- 노드는 1부터 시작하므로 array, visit는 n+1의 길이를 가져야 한다.
- DFS를 이용하여 노드를 탐색한다. main에서 모든 노드들을 체크하며 방문하지 않은 곳에서 탐색을 시작한다. 탐색을 시작할 때에는 cnt를 늘려 시작 노드의 개수를 체크해야한다.
- DFS에서는 최단 거리를 구하는 것이 목적이 아니므로 visit[i]=true한 값을 false로 바꿀 필요는 없다.
- 시작 노드들의 개수 cnt를 출력한다.