[BOJ] 백준 11724 연결 요소의 개수-java

문제

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

입력

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

출력

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

 

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

11724번: 연결 요소의 개수

 

풀이

기본적인 bfs 혹은 dfs문제이다. 이 문제를 풀기 위해 알아야 할 개념으로는 그래프, 인접 행렬, 인접 리스트, dfs, bfs가 있다. 모두 다 알아야 하는 건 아니지만 인접 행렬/인접 리스트 중 하나를 선택하고 dfs/bfs 중 하나를 선택하여 푸는 것이 문제의 의도에 맞게 푸는 방법이라고 생각한다.

간단하게 문제를 풀어가는 방법에 대해 이야기해보자. 그래프의 정점과 연결하는 간선을 입력받았을 때 몇 개의 그룹으로 나뉘는지를 알아내면 된다. 연결 요소라는 것을 쉽게 그룹이라고 표현하겠다.

두번째 줄부터 간선을 입력받는데 "1 2"를 입력받았다면 1과 2를 이어주는 간선이 하나 있다고 생각하면 된다. 

위와 같이 1,2,5가 하나의 그룹이 되고 3,4,6이 하나의 그룹이 되어 답은 2가 된다.

1,2,5와 3,4,6사이에는 간선이 없기 때문에 분리되어 있다고 할 수 있는 것이다. 그렇다면 분리되어 있는 것은 어떻게 알까?

dfs 혹은 bfs를 통해 알 수 있다. 그 중 dfs를 예로 설명해보자.

정점 1에 방문한다. 방문해서 1과 연결 된 정점을 알아낸다. (adjList라는 간선의 정보를 담는 배열을 통해 알 수 있다. adjList[1] -> [2,5] 이렇게 구성되어 있다.) 아래의 코드를 통해 정점 두 개(1,2라고 해보자)가 들어오면 adjList[1].add(2); adjList[2].add(1); 이런 코드를 통해 서로 연결되어 있음을 알 수 있다. 이것이 인접 리스트이다. 

adjList[vertex1].add(vertex2);
adjList[vertex2].add(vertex1);

 

1과 연결된 정점은 2,5이다. 그럼 그 중 하나의 정점에 방문한다. 2에 방문한다면 2와 연결된 정점을 알아내고 1은 이전에 방문했기에 방문하지 않은 5에 방문한다. 그럼 현재 방문한 정점은 1,2,5가 되고 5와 연결된 정점은 모두 방문한 정점이기에 다시 2로 돌아간다. 그럼 2와 연결된 정점도 모두 방문했기에 다시 1로 돌아가고 1 또한 연결된 정점 2,5에 방문했기에 하나의 그룹이 끝났다는 것을 알 수 있다.

그럼 그 다음은 방문하지 않은 정점을 다시 찾는 것이다. 방문하지 않은 정점 3,4,6이 있다. 그중 3에 먼저 방문해보자. 3에 방문하여 연결된 정점을 알아보니 4,6이 있다. 그중 하나인 4에 먼저 방문해본다. 4에 방문하니 연결된 정점은 3밖에 없고 3은 이전에 방문한 노드이니 더 방문해야 할 곳이 없기에 3으로 돌아간다. 그럼 3의 입장에서는 4는 방문하였고 6은 방문하지 않았다. 그렇기에 6에 방문하고 6은 연결된 정점이 3뿐인데 이미 방문했으므로 다시 3으로 돌아간다. 3으로 돌아와서 보니 연결된 정점은 4,6인데 다 방문한 상태이다. 그렇기에 하나의 그룹이 끝났다. 

그렇게 두번째 그룹도 다 방문한 뒤 방문하지 않은 정점이 있나 살펴보고 없다면 종료하면 된다. 아래는 하나의 그룹에 정점을 방문하고 오는 dfs 메서드를 호출하고 메서드가 끝나면 answer이라는 연결 요소의 총 수를 저장하는 변수의 값을 증가시키는 코드이다. 

for(int i = 1; i < n+1; i++) {
	if(!visited[i]) {
		dfs(i);
		answer++;
	}
}

위와 같이 정점의 개수만큼 반복문을 돌며 방문하지 않은 정점이 있다면 그 정점과 연결된 그룹을 다 방문하고 돌아와서 answer를 증가시키면 총 몇 개의 연결 요소가 있는지 알 수 있다.