[백준] 11724 : 연결 요소의 개수 JAVA 풀이

 

 

우선 연결 요소가 무엇인지 몰라서 검색을 해봤다.

 

그래프 상에서 이어져 있는 모든 정점들이 있을 때 그것을 하나의 연결 요소라고 한다.

따라서 위 이미지에서는 3개의 연결 요소가 존재한다고 할 수 있다.

 

연결 요소의 개수를 구하는 방법은 간단하다.

아직 방문하지 않은 정점에 대해 BFS 또는 DFS를 수행하고

그때마다 연결 요소의 개수를 추가해주면 된다.

 

시작 정점에 대해 BFS 또는 DFS를 수행하면 인접 정점들을 모두 방문하게 되는데

이것은 하나의 연결 요소를 훑은 것과 같은 의미이기 때문이다.

 

import java.io.*;
import java.util.*;
public class Main {
	static int[][] graph;
	static boolean[] visit;
	static int N;
	public static void main(String[] args) throws IOException{
		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());
		
		graph = new int[N+1][N+1];
		visit = new boolean[N+1];
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			graph[x][y] = 1;
			graph[y][x] = 1;
		}
		
		int cnt = 0;
		
        // 1번 ~ N번 정점에 대해 아직 방문하지 않은 정점이면 BFS 수행
        // BFS 수행 후 연결 요소의 개수 +1
		for(int i=1;i<N+1;i++) {
			if(visit[i]==false) {
				bfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);
		
	}
	public static void bfs(int v) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(v);
		visit[v] = true;
		
		while(!q.isEmpty()) {
			int tmp = q.poll();
			
			for(int i=1;i<N+1;i++) {
				if(graph[tmp][i]==1&&visit[i]==false) {
					q.offer(i);
					visit[i] = true;
				}
			}
		}
	}

}