[Java | 백준 11724번] 연결 요소의 개수

백준 11724번 www.acmicpc.net/problem/11724

연결요소(Connected Component)

아래 사진에서 보면 등가관계의 구성요소가 총 3개임을 알 수 있다. 즉, 연결요소 또는 구성요소가 3개 있다고 표현한다.

그래프에서 하나의 노드에서 출발해서 연결된 그래프가 하나의 연결요소이자, 이 전체를 3개의 구성요소로 된 하나의 그래프라고도 표현할 수 있다.

풀이

DFS, BFS 풀이가 모두 가능하다. 아래 풀이는 DFS 풀이이다.

1. 일단 변수들을 초기화해준다.

num 은 정점의 수, path는 간선의 수, node 는 실제 간선의 양 끝점을 확인하는 boolean 값, visit 는 방문여부를 표시한다.

cnt 는 visit 값이 false 일 때, 그 수를 세어준다.(출력값)

2. 방향성이 없는 그래프 이동으므로 node[n][m] 값과 node[m][n] 모두 true; 값을 준다.

3.  static void path(int x) 메서드를 먼저 살펴보자. 메서드의 실행은 visit[x] 값이 false 일 때 실행되는데 방문하지 않은 간선이므로, visit[x] 를 true 로 바꿔준다. 그리고 node[x][i] 값이 있으나 visit[x] 값이 false 라면, 즉 연결된 노드인데 방문하지 않았다면 다시 재귀형태로 path() 메서드를 실행한다.

정리하자면 연결된 간선이 있고 방문하지 않았다면 다 방문할 수 있도록 하는 것이다.

4. 3 번의 내용처럼 연결된 간선을 따라 방문하면 true 가 되므로  DFS_11724 클래스의 for 문에서는 방문하지 않은 경우를 발견했을 때, cnt 를 세면서 연결 요소의 개수를 파악할 수 있다.