[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)

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

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

 코드 실행 결과 

1. BFS 코드 실행 결과

2. DFS + Recursion 코드 실행 결과

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

---

 후기 

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

---

 문제 원본 

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

11724번: 연결 요소의 개수

 알고리즘 분류 

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