Baekjoon 11724 연결 요소의 개수 JAVA

11724번: 연결 요소의 개수

문제

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

 

입력

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

출력

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

풀이

방향 없는 그래프는 양쪽으로 이어져 있는 그래프이다.

이 문제에서는 정점의 개수가 1000개 이기에 2차원 배열을 이용하여 연결 요소들을 표현해도 괜찮다고 판단하였음.

입력받는 모든 요소들을 2차원 배열을 이용하여 표현을 해주고

너비 우선 탐색 BFS를 이용하여 하나의 시작점으로 부터 모든 이동가능한 요소들을 방문한다.

이때 하나의 시작점으로부터 이어지는 모든 방문 정점들은 하나의 연결 요소이기에 연결 요소의 개수를 증가한다.

 

이를 모든 정점들을 탐색하면서 존재하는 모든 연결 요소의 개수를 탐색한다.

코드

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

public class Main {
	static boolean [][] graph;
	static boolean [] chk;
	static int n;
	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());
		int m=Integer.parseInt(st.nextToken()), ans=0;
		chk = new boolean [n+1];
		graph = new boolean [n+1][n+1];
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken()), b=Integer.parseInt(st.nextToken());
			graph[a][b]=graph[b][a]=true;
		}
		for(int i=1;i<=n;i++) {
			if(!chk[i]) {
				ans++;
				BFS(i);
			}
		}
		System.out.println(ans);
	}
	static void BFS(int s) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(s);
		while(q.size()>0) {
			int cur=q.poll();
			for(int i=1;i<=n;i++) {
				if(!chk[i] && graph[cur][i])
				{
					chk[i]=true;
					q.add(i);
				}
			}
		}
	}
}