[JAVA / 자바] 백준 11724번 - 연결 요소의 개수 (실버 2)

 문제 

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

---

 입력 

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

---

 출력 

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

---

 

---

 문제 접근 방법 

이번 문제는 입력으로 주어진 그래프의 연결 요소의 개수를 파악하는 문제이다.

이때, 연결 요소란? 한 정점에서 출발하여 도착할 수 있는 정점들의 집합이라 생각하면 쉽다.

이게 무슨 의미냐면 정점 V1과

간선을 통해 해당 정점 Vn에 도착할 수 있다면 같은 연결 요소이지만,

간선을 통해 정점 Vn에 도착할 수 없다면 다른 연결 요소로 판단된다.

연결 요소 = {V1, V2, V3, V5}, {V4, V6, V7}

위 그래프에는 총 2개의 연결 요소가 있다고 말할 수 있는 것이다.

따라서 위를 찾을 수 있는 방법은

  1. 너비 우선 탐색

  2. 깊이 우선 탐색

    2-1. 재귀

    2-2. 스택 + 반복문

으로 풀어볼 수 있다. 세 가지 방법 모두 논리는 동일하다.

모든 정점에 대해 연결된 정점을 모두 탐색하는데 첫 시작은 아무 정점이나 잡아도 무관하다. (단, 모든 정점이 한 번씩 시작 정점이 되어 탐색을 해주어야 한다.)

 

1) 무난하게 첫 시작 정점을 V1으로 잡으면 위 세 가지 알고리즘을 사용하여 탐색했을 때, V1, V2, V3, V5가 탐색이 될 것이다. (시작점을 새로 지정해 알고리즘을 첫 실행할 시 연결 요소 카운팅)

2) 그렇다면 탐색된 네 가지 정점을 방문 처리해주고 이 정점들은 탐색 시작 정점에서 제외한다.

3) 제외하고 남은 탐색이 되지 않은 정점 중에 하나를 골라 시작 정점으로 설정하고 1 ~2번을 반복 실행해주면 된다.

 

이때 주의할 점은 탐색을 할 때마다 카운팅 해주어 연결 요소의 개수를 체크해주어 모든 정점이 방문이 완료되었을 때, 이를 출력해주면 문제는 해결된다.

(∵ 같은 연결 요소는 한 번의 탐색이 끝나게 되면 모두 방문 처리되어 체크되기 때문 => 한 번의 탐색 = 한 개의 연결 요소 발견)

---

 JAVA 코드 풀이 

1. 너비 우선 탐색(BFS, Breath First Search)

	import java.util.*;
	import java.io.*;
	public class Main {
	static int n;
	static boolean node[][], visited[];
	static Queue<Integer> queue = new LinkedList<>();
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer init = new StringTokenizer(br.readLine());
	n = Integer.parseInt(init.nextToken());
	int m = Integer.parseInt(init.nextToken());
	node = new boolean[n+1][n+1]; // 그래프 저장할 배열
	int v1, v2;
	while(m-- > 0) { // 방향이 없는 간선 입력
	StringTokenizer st = new StringTokenizer(br.readLine());
	v1 = Integer.parseInt(st.nextToken());
	v2 = Integer.parseInt(st.nextToken());
	node[v1][v2] = true;
	node[v2][v1] = true;
	}
	visited = new boolean[n+1]; // 정점 방문 여부 체크할 배열
	int cnt = 0;
	for(int i=1; i<=n; i++)
	if(!visited[i]) {
	cnt++; // 새로운 연결 요소 찾음
	bfs(i); // 새로 찾은 연결 요소에 속해있는 정점들 탐색
	}
	System.out.println(cnt);
	}
	static void bfs(int sV) {
	queue.add(sV);
	visited[sV] = true;
	int vn;
	while(!queue.isEmpty()) {
	vn = queue.remove();
	for(int i=1; i<=n; i++)
	if(node[vn][i] && !visited[i]) {
	queue.add(i);
	visited[i] = true;
	}
	}
	}
	}

view raw 11724_BFS.java hosted with ❤ by GitHub

2. 깊이 우선 탐색(DFS, Depth First Search) - 재귀(Recursion)

	import java.util.*;
	import java.io.*;
	public class Main {
	static int n;
	static boolean node[][], visited[];
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer init = new StringTokenizer(br.readLine());
	n = Integer.parseInt(init.nextToken());
	int m = Integer.parseInt(init.nextToken());
	node = new boolean[n+1][n+1]; // 그래프 저장할 배열
	int v1, v2;
	while(m-- > 0) { // 방향이 없는 간선 입력
	StringTokenizer st = new StringTokenizer(br.readLine());
	v1 = Integer.parseInt(st.nextToken());
	v2 = Integer.parseInt(st.nextToken());
	node[v1][v2] = true;
	node[v2][v1] = true;
	}
	visited = new boolean[n+1]; // 정점 방문 여부 체크할 배열
	int cnt = 0;
	for(int i=1; i<=n; i++)
	if(!visited[i]) {
	cnt++; // 새로운 연결 요소 찾음
	visited[i] = true;
	connected(i); // 새로 찾은 연결 요소에 속해있는 정점들 탐색
	}
	System.out.println(cnt);
	}
	static void connected (int vertex) {
	for(int i=1; i<=n; i++)
	if(node[vertex][i] && !visited[i]) {
	visited[i] = true;
	connected(i);
	}
	}
	}

view raw 11724_DFS_recursion.java hosted with ❤ by GitHub

3. 깊이 우선 탐색(DFS, Depth First Search) - 스택(Stack) + 반복문

	import java.util.*;
	import java.io.*;
	public class Main {
	static int n;
	static boolean node[][], visited[];
	static Stack<Integer> stack = new Stack<>();
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer init = new StringTokenizer(br.readLine());
	n = Integer.parseInt(init.nextToken());
	int m = Integer.parseInt(init.nextToken());
	node = new boolean[n+1][n+1]; // 그래프 저장할 배열
	int v1, v2;
	while(m-- > 0) { // 방향이 없는 간선 입력
	StringTokenizer st = new StringTokenizer(br.readLine());
	v1 = Integer.parseInt(st.nextToken());
	v2 = Integer.parseInt(st.nextToken());
	node[v1][v2] = true;
	node[v2][v1] = true;
	}
	visited = new boolean[n+1]; // 정점 방문 여부 체크할 배열
	int cnt = 0;
	for(int i=1; i<=n; i++)
	if(!visited[i]) {
	cnt++; // 새로운 연결 요소 찾음
	dfs(i); // 새로 찾은 연결 요소에 속해있는 정점들 탐색
	}
	System.out.println(cnt);
	}
	static void dfs(int sV) {
	stack.add(sV);
	visited[sV] = true;
	int vn;
	while(!stack.isEmpty()) {
	vn = stack.pop();
	for(int i=1; i<=n; i++)
	if(node[vn][i] && !visited[i]) {
	stack.add(i);
	visited[i] = true;
	}
	}
	}
	}

view raw 11724_DFS_stack.java hosted with ❤ by GitHub

 코드 실행 결과 

1. BFS 코드 실행 결과

2. DFS + Recursion 코드 실행 결과

3. DFS + Stack + 반복문 코드 실행 결과

---

 후기 

이번 문제는 그래프 탐색의 기초적인 문제로 큰 어려움 없이 해결 가능한 문제라는 생각이 든다.

---

 문제 원본 

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 알고리즘 분류 

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색