[백준] 11724번 : 연결 요소의 개수 자바(JAVA) 풀이 - 연결 요소(Connected Component) 란?

연결요소가 무엇인지 알아보고 관련된 문제를 풀어보도록 하자!

연결 요소(Connected Component) 란?

무방향 그래프 내에서 다음 두 조건을 만족하는 정점들의 최대 집합을 연결 요소라고 한다. 그래프 내에서 연결되어 있는 정점들을 한 그룹으로 묶으면 생기는 그룹이 연결 요소이다.

 

조건 1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.

조건 2. 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

 

 

만약 정점이 1~6까지 있다고 쳤을 때 그림과 같이 나누어진 각각의 그래프를 연결 요소라고 한다. 노란색 연결 요소 1, 초록색 연결 요소 1로 전체 그래프에 연결 요소가 2개 있다고 볼 수 있다.

 

연결 요소 문제 탐색

연결 요소의 개수는 DFS/BFS로 구할 수 있다. 

 

한 정점에서 시작해 연결된 정점들을 탐색하는데 아직 정점에 방문하지 않았으면 재귀적으로 탐색한다.

이 탐색 과정에서 만나게 되는 모든 정점들을 한 집합에 넣으면 그게 바로 연결 요소가 된다.

 

DFS/BFS는 간선이 연결되어 있는 정점들 사이만 탐색할 수 있기 때문에, 끊겨 있는 다른 연결 요소 부분은 탐색이 안된다.

따라서 연결 요소의 개수는 한 사이클이 돌고 나서 개수를 카운트해주면 된다.

 

연결 요소 관련 문제

---

---

 

가능한 시간복잡도

입력 범위 ( 1 ≤ N ≤ 1,000 , 0 ≤ M ≤ N*(N-1)/2 )

최대 정점 N개에 대해 탐색을 진행한다. 사이클을 확인하는 과정에서 간선 탐색을 진행하게 되는데, 한 번 방문한 간선을 다시 방문하지 않고 간선이 양방향이므로 최대 2M개의 탐색이 진행된다.

즉, 최종 시간 복잡도는 O(N+2M) 이 된다.

 

---

코드 설계하기

• 입력받은 그래프에 대한 정보를 인접리스트로 저장한다.
• visited 배열을 만들어 방문 여부를 체크해준다. (기본값 False)
• 방문하지 않은 경우

• 방문 처리
• 해당 정점과 연결된 정점들 방문처리
• 카운드 +1

 

---

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph; // 인접리스트로 선언
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 정점의 개수
		int M = Integer.parseInt(st.nextToken()); // 간선의 개수
		int count = 0; //연결요소 개수
		
		graph = new ArrayList<ArrayList<Integer>>();
		visited = new boolean[N+1];
		
		for(int i=0;i<N+1;i++) {
			graph.add(new ArrayList<Integer>()); // 그래프 인덱스 초기화
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
            // 양방향 그래프로 그래프 저장
			graph.get(u).add(v); 
			graph.get(v).add(u);
		}
		
		for(int i=1;i<N+1;i++) {
        	// 방문하지 않은 경우
			if(!visited[i]) {
				dfs(i);
				count++;
			}
		}
		
		System.out.println(count);
		
	}
	
	static void dfs(int start) {
		visited[start] = true;
		
        // 해당 정점과 연결된 정점 탐색
		for(int next:graph.get(start)) {
			if(!visited[next]) {
				dfs(next);				
			}
		}
	}
}