[BOJ] 11724. 연결 요소의 개수

문제

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

입력

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

출력

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

예제 입력

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력

2

코드

// 연결 요소의 개수

package _00_TodayProblem.tp03._00_inflearn._02_11724;

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

public class Solution {
	final static int MAX = 1000 + 10;
	static boolean[][] graph;
	static boolean[] visited;
	static int N, M;
	static int answer;

	public static void dfs(int idx) {
		visited[idx] = true;

		for (int i = 1; i <= N; i++) {
			if (visited[i] == false && graph[idx][i]) {
				dfs(i);
			}
		}

	}

	public static void main(String[] args) throws IOException {
		// 0. 입력과 출력
		System.setIn(new FileInputStream("src/_00_TodayProblem/tp03/_00_inflearn/_02_11724/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		graph = new boolean[N + 1][N + 1];
		visited = new boolean[N + 1];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph[u][v] = true;
			graph[v][u] = true;
		}

		// dfs를 어떻게 시작할 것인가가 중요함.
		for (int i = 1; i <= N; i++) {
			if (visited[i] == false) {
				dfs(i);
				answer++;
			}
		}

		bw.write(String.valueOf(answer));
		bw.close();
		br.close();
	}
}

풀이

• 입력 및 출력, 초기화, 연결 정보 저장까지 바이러스 문제와 동일하기에 코드가 전반적으로 비슷합니다.
• 바이러스는 연결된 정점의 갯수를 구하는 거였다면, 이 문제는 연결 요소의 개수 즉, 연결되어있는 덩어리가 몇 개인지를 출력하는 것이 문제의 요건입니다.
• 그렇기 때문에, 그래프를 그려보았을 때 연결된 정점 그룹들이 나누어져있는 것을 확인할 수 있습니다.
• 이 말은 즉, dfs를 바이러스와 동일하게 방문하면, 방문하지 않게 되는 연결된 정점 그룹이 있다는 이야기입니다.
• 따라서, 조건을 충족시키기 위해 출력을 다음과 같이 작성합니다.

💡 dfs 출력

• 조건을 충족시키려면 visited배열을 모두 채워야합니다. 즉, 모든 정점들을 방문해야한다는 것입니다.
• 따라서, 모든 정점들을 방문하기 위해서 정점의 개수만큼 dfs(i)함수를 반복합니다.
• 이 때, 이미 방문했던 정점들은 방문하지 않아도 되기 때문에 visited[i] == false라는 조건을 걸어줍니다.
• 마지막으로 for문에서 dfs(i)함수를 반복한 횟수가 곧 연결 요소의 개수가 되기 때문에, answer++;를 실행합니다.

💡 dfs 구현

• 이제 마지막으로 dfs를 구현하면 끝입니다.
• 바이러스와 dfs함수 구현은 비슷하나, 다른 점은 방문 여부만 확인하면 된다는 점입니다.
• 그래서 dfs 함수에는 visited[idx] 값만 수정하는 로직이 담겨있습니다.