DFS/BFS 백준 알고리즘 자바 11724 ‘연결 요소의 개수’ 문제풀이

Problem

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

Input 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

Output 첫째 줄에 연결 요소의 개수를 출력한다.

Solution

먼저 풀었던 DFS와 BFS 문제에서 dfs 부분 중 return값을 추가해주면 된다. main에서 dfs 함수를 호출해줄 때가 새로운 정점을 시작하는 단계이므로 카운트용 변수 cnt를 증가시켜준다.

Code

import java.util.Scanner;
public class Main {	
	static int[][] g;
	static boolean[] visit;
	static int n;
	
	private static int dfs(int v) {
		if(visit[v]) return 0;
		
		visit[v] = true;
		for(int i = 1; i <= n; i++) if(g[v][i] != 0) dfs(i);
		return 1;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		int cnt = 0, m = scan.nextInt();
		
		g = new int[n+1][n+1]; visit = new boolean[n+1];
		while(m-- > 0) {
			int u = scan.nextInt(), v = scan.nextInt();
			g[u][v] = g[v][u] = 1;
		}
		
		for(int i = 1; i <= n; i++) cnt += dfs(i);
		System.out.print(cnt);
	}
}