코딩 테스트 [탐색] - 연결 요소의 개수 구하기

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

(시간 제한 3초)

---

입력

1번째 줄에는 노드의 개수 N(1 ≤ N ≤ 1,000)과 에지의 개수 M(0 ≤ M ≤ N x (N-1)/2), 2번째 줄부터 M개의 줄에 에지의 양 끝 점 u와 v가 주어진다(1 ≤ u, v ≤ N, u ≠ v). 같은 에지는 한 번만 주어진다.

출력

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

예제 입력
6 5 // 노드 가수, 에지 개수
1 2
2 5
5 1
3 4
4 6

예제 출력
2

---

1단계 - 문제 분석하기

노드의 최대 개수가 1,000이므로 시간 복잡도 O($N^{2}$)이하의 알고리즘을 모두 사용할 수 있다.
연결 요소는 에지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다.

2단계 - 손으로 풀어 보기

1 그래프를 인접 리스트로 저장하고 방문 배열도 초기화한다. 방향이 없는 그래프이기 때문에 양쪽 방향으로 에지를 모두 저장한다.

2 임의의 시작점에서 DFS를 수행한다. 현재의 경우 1을 시작점으로 정했다.
탐색을 마친 후 방문한 곳은 1, 2, 5가 된다.

3 아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행한다. 현재의 경우 3, 4, 6 순서로 탐색을 마쳤다.
모든 노드를 방문했으므로 전체 탐색을 종료한다.

4 1~3 과정을 통해 총 2번의 DFS가 진행되었다. 즉 연결 요소의 개수는 2개이다.

만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되었을 것이다. 다시 말해 모든 노드를 탐색하는 데 실행한 DFS의 실행 횟수가 곧 연결 요소의 개수이다.

3단계 - sudo코드 작성하기

N(노드 개수) M(에지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)

for(N의 개수만큼 반복)
{
	A 인접 리스트의 각 ArrayList 초기화하기
}

for(M의 개수만큼 반복)
{
	A 인접 리스트에 그래프 데이터 저장하기
}

for(N의 개수만큼 반복하기)
{
	if(방문하지 않은 노드가 있으면)
    {
    	연결 요소 개수++
        DFS 실행
    }
}

// DFS 구현 부분
DFS {
	if(현재 노드 == 방문 노드)
    	return
    
    visited 배열에 현재 노드 방문 기록하기
    
    현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기    // 재귀 함수 형태
}

4단계 - 코드 구현하기

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

public class Q23 {
    static ArrayList<Integer>[] A;
    static boolean visited[];
    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());
        A = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for(int i = 1; i <= N; i++)
            A[i] = 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());

            A[u].add(v);
            A[v].add(u);
        }

        int count = 0;

        for(int i = 1; i <= N; i++){
            if(!visited[i]){
                count++;
                DFS(i);
            }
        }

        System.out.println(count);
    }

    static void DFS(int v){
        if(visited[v])
            return;

        visited[v] = true;

        for(int i : A[v]){
            if(visited[i] == false)
                DFS(i);
        }
    }

}

---

• Do it! 알고리즘 코딩테스트 자바 편