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

• 문제 링크

11724번: 연결 요소의 개수

 

• 풀이 과정

무향 그래프의 정점이 모두 연결되어 있고 하위 그래프와 나머지 그래프 사이에 연결이 없을 경우,

이를 연결 요소라 명칭하며 아래의 예시에서는 (0, 1, 2, 3), (4, 5, 6), (7, 8) 총 3개의 연결 요소가 존재한다.

Connected Components

이러한 연결 요소의 개수는 dfs / bfs 로 탐색하여 구할 수 있으며

해당 문제에선 연결 리스트를 활용한 dfs로 풀이하였다.

 

모든 노드를 시작점으로 탐색을 시도하고 해당 노드가 방문하지 않았을 경우,

탐색이 수행되며 연결 요소의 개수를 의미하는 cnt 변수에 1를 더한다.

 

이때 탐색을 수행할 함수의 반환 값은 boolean 형으로,

매개 변수로 받은 노드의 방문 여부에 따라 true / false 값을 반환하고,

true 일 시 해당 노드를 시작점으로 dfs 탐색을 수행하며 이와 연결된 모든 노드를 방문함으로 표시한다.

 

이로써 해당 연결 요소의 모든 노드는 시작점이 될 수 없음을 의미하며,

이를 제외한 방문하지 않은 노드가 있을 시 해당 노드가 시작점인 새로운 연결 요소로써 탐색을 수행한다.

 

각각의 연결 요소의 탐색이 수행될 때마다 1이 더해진 cnt 변수를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static List<List<Integer>> list = new ArrayList<>();
	static boolean[] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		visit = new boolean[n + 1];

		for (int i = 0; i < n + 1; i++)
			list.add(new ArrayList<>());

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());

			list.get(y).add(x);
			list.get(x).add(y);
		}

		int cnt = 0;
		for (int i = 1; i < n + 1; i++) {
			if (dfs(i))
				cnt++;
		}

		bw.write(cnt + "\n");
		bw.flush();
	}

	private static boolean dfs(int node) {
		if (visit[node])
			return false;
		else {
			visit[node] = true;
			for (int i = 0; i < list.get(node).size(); i++) {
				int next = list.get(node).get(i);
				if (!visit[next])
					dfs(next);
			}

			return true;
		}
	}

}