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

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

 

풀이

1. DFS 혹은 BFS를 이용하는 간단한 문제이다. 나는 DFS로 구현하였다.
2. 먼저 주어진 간선 정보를 인접 리스트(ArrayList 배열)로 저장해준다. (편의상 1번 index부터 저장하도록 했다)
3. 모든 정점들을 확인하며 방문하지 않은 노드가 있을 때마다 DFS를 실행한다.
   1. DFS가 한 번 끝날때마다 연결된 정점들에 대해 탐색이 끝나므로 그때마다 count를 해주면 된다.
   2. 모든 정점을 방문했다면 count값을 출력하고 종료.

import java.util.*;

public class Main {
	static boolean check[];
	static ArrayList[] adjlist;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int count = 0;
		check = new boolean[n+1];
        
        //인접리스트 구현
        adjlist = (ArrayList[]) new ArrayList[n+1];
		for(int i=0; i<n+1; i++) {
			adjlist[i] = new ArrayList();
		}
		for(int i=0; i<m; i++) {
			int vertex1 = sc.nextInt();
			int vertex2 = sc.nextInt();
			adjlist[vertex1].add(vertex2);
			adjlist[vertex2].add(vertex1);
		}
		
        //모든 정점 탐색
		for(int i=1; i<n+1; i++) {
			if(check[i] == false) {
				dfs(i);
				count++;
			}
		}
		System.out.println(count);
	}
	
	static void dfs(int v) {
		check[v] = true; //방문 체크
        //해당 정점에 연결되어 있는 정점들을 방문
		for(int i=0; i<adjlist[v].size(); i++) {
			int x = adjlist[v].get(i);
			if(check[x] == false)
				dfs(x);
		}
	}
}