[ 백준 11724 / Java ] 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

 

풀이

DFS를 사용해서 풀어보았다.

DFS와 BFS 문제에서 DFS를 풀이한 것과 비슷하다. 

다만 차이점은 DFS와 BFS에서는 첫 번째 노드와 연결되어있는 노드의 숫자만 뽑아냈다.

여기서는 DFS가 다 연결되어있지 않다. 그러므로 연결되지 않은 그룹들의 개수를 뽑아내야 한다.

 

예제 입력1에서 결괏값은 2이다.

그 이유는 1,2,5가 서로 연결되어있고 3,4,6이 서로 연결되어 총그룹이 2개이기 때문이다.

 

import java.util.*; import java.io.*;   public class Main {     static int N; //정점 개수     static int M; // 간선 개수     static boolean[] isVisit; //방문 체크     static ArrayList<Integer> arr[];       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());         arr = new ArrayList[N+1];         isVisit = new boolean[N+1];         int count = 0; // 연결 요소 개수         for (int i = 0; i < arr.length; i++) {             arr[i] = new ArrayList<>();         }         // 인점행렬 입력         for (int i = 0; i < M; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt((st.nextToken()));             arr[a].add(b);             arr[b].add(a);         }         for(int i = 1; i < N+1; i++) {             if(!isVisit[i]) { // 방문한적 없는 노드라면 DFS                 dfs(i);                 count++;             }         }         System.out.println(count);     }     public static void dfs(int index) {         isVisit[index] = true;         for (int i:arr[index]) {             if(!isVisit[i]) {                 dfs(i);             }         }     } } Colored by Color Scripter

cs