[백준] 11724 연결 요소의 개수 - DFS(깊이우선탐색) JAVA

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

코드설명

DFS(깊이우선탐색) 를 활용합니다.

 

각 연결 요소의 개수를 세기 위해서, 총 나눠진 그래프의 개수를 구하는 문제입니다. 

DFS를 활용하여, 방문처리를 진행하면 됩니다.

 

이 문제의 경우 물론 BFS를 사용해도 가능합니다. (사실상 DFS로 풀 수 있는 문제는 모두 BFS로 풀 수 있습니다.)

 

유니온 파인드로도 가능합니다. 

다만, 유의할점은, 마지막에 모든 정점들에 대해 find(i)로 각 정점들의 루트값을 찾아내야하는데, 이떄 HashSet으로 중복제거를 통한다면 나눠진 그래프의 개수를 손쉽게 알 수 있습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] arr;
	static int[][] matrix;
	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());
		matrix = new int[N][N];
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			matrix[u][v] = 1;
			matrix[v][u] = 1;
		}
		
		boolean[] visited = new boolean[N];
		
		for(int i=0;i<N; i++) {
			if(visited[i] == false) {
				visited[i] = true;
				int temp = dfs(0, i, visited) + 1;
				if(temp > 0) {
					answer += 1;
				}
			}
		}
		System.out.println(answer);
	}
	
	static int dfs(int depth, int now, boolean[] visited) {
		
		int ret = 0;
		for(int next = 0; next < N; next++) {
			if(now == next) continue;
			if( matrix[now][next] == 1 && visited[next] == false) {
				visited[next] = true;
				ret += dfs(depth + 1, next, visited) + 1;
			}
		}
		
		return ret;
	}
	
}