[java][boj][s2] 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) 같은 간선은 한 번만 주어진다.

출력

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

풀이

오랜만에 푼 dfs라 풀이 방법을 다 잊어버려서 틀 짜는 시간보다 디버깅 시간이 더 걸렸다 전체적인 틀은 dfs와 같지만, 다른 점은 dfs 함수 밖에서 for문을 돌려 개수를 세어줘야 한다는 것이다

코드

package A형대비;

import java.io.*;
import java.util.*;

public class s2_11724_연결요소의개수 {
	static int N, M, ans;
	static int[][] arr;
	static boolean[] checked;
	
	public static void main(String[] args) throws Exception {
		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 int[N][N];
		checked = new boolean[N];
		
		for(int i = 0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
            //방향이 없는 그래프이므로 양쪽을 전부 이어 준다
			arr[u-1][v-1] = arr[v-1][u-1] = 1;
		}
		
		for(int i = 0; i<N; i++) {
			if(!checked[i]) {
				dfs(i);
                //탐색이 끝나면 개수 추가
				ans++;
			}
		}
        
		System.out.println(ans);
	}

	private static void dfs(int start) {
		for(int i = 0; i<N; i++) {
			checked[start] = true;
            //방문한 적 없고, 간선이 이어져 있으면 탐색
			if(!checked[i] && arr[start][i] == 1) dfs(i);
		}
	}
}

결과

 

#자바 #java #boj #백준 #알고리즘