[백준_11724번] 연결 요소의 개수

https://www.acmicpc.net/problem/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) 같은 간선은 한 번만 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_11724 {
	static ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
	static int n,m,result=0;
	static boolean[] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		visited=new boolean[n+1];
		for(int i=0;i<=n;i++)
			graph.add(new ArrayList<>());
		
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		// 방문하지 않은 노드를 시작으로 연결된 모든 노드 탐색
		for(int i=1;i<=n;i++) {
			if(!visited[i]) {
				dfs(i);
				result++; // 집단의 개수 증가
			}
		}
		System.out.println(result);
	}
	
	// 연결된 노드를 모두 방문처리 하는 함수
	static void dfs(int start) {
		for(int next:graph.get(start)) {
			if(!visited[next]) {
				visited[next]=true;
				dfs(next);
			}
		}
	}
}

 

[고찰]

 이번 문제는 그래프 문제로 연결된 노드의 덩어리를 찾는 문제였다. DFS 알고리즘으로 탐색 시작 노드와 연결된 모든 노드를 방문처리 해주면 되는 간단한 문제였다.