백준 11724

문제

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

입력

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

풀이코드

package baekjoon.dfs;

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

public class Q11724 {

    static int N;
    static int M;
    static boolean[] visited;
    static int[][] lines;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();

        StringTokenizer st = new StringTokenizer(s, " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1];
        lines = new int[N+1][N+1];

        for (int i = 0; i < M; i++) {
            String s1 = br.readLine();
            st = new StringTokenizer(s1, " ");

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            lines[num1][num2] = lines[num2][num1] = 1;
        }

        int result = 0;
        for (int i = 1; i < lines.length; i++) {
            if (!visited[i]) {
                result += dfs(i);
            }
        }

        System.out.println(result);
    }

    public static int dfs(int index) {
        visited[index] = true;
        for (int i = 0; i < lines.length; i++) {
            if (lines[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
        return 1;
    }
}

해설

그래프탐색의 기초적인 문제이다.

DFS로 풀이하였다.

노드 탐색에서 DFS 풀이의 핵심은 다음과 같다

• 노드 방문 여부를 저장하는 배열
• 각 노드끼리 연결을 저장하는 배열 (2차원배열)

배열의 크기는 노드의 최종번호 + 1 로 설정한다.

이유는 주로 알고리즘 문제에선 1~N번으로 노드의 번호가 주어지고,

배열의 인덱스는 0번부터 시작하기 때문에 노드 개수 그대로로 배열크기를 설정할 경우 노드와 배열을 매핑시키기 위해 노드번호-1 등의 중간처리과정이 필요하기 때문이다.

편의상 배열의 인덱스와 노드번호를 그대로 매핑시킬 수 있게 하기 위해 배열의 크기를 노드의 최종번호 + 1 로 설정한다.

방문 여부를 체크하는 배열 visited[]는 각 인덱스(노드번호)에 true, false를 저장하는 boolean 형 배열이고,

노드를 있는 lines[][] 배열은 노드끼리 연결된경우 1을 저장하는 int형 배열이다.

사실 연결 여부만 저장하면 되니 배열 타입은 크게 중요하지 않다.

lines[][] 배열의 구조를 간단한 예시로 살펴보자

1-2-3-1 로 연결된 노드가 있다고 가정해보자.
그럼 배열에는 다음과 같이 저장된다.

노드의 개수 : 3 (1번, 2번, 3번)
lines = new int[4][4] 로 선언 // 최종번호 + 1
연결 입력 : 1 2 , 2 3 , 3 1

연결된 노드끼리는 값 1을 저장한다.
lines[1][2] = lines[2][1] = 1;
lines[2][3] = lines[3][2] = 1;
lines[3][1] = lines[1][3] = 1;

저장된 구조는 다음과 같다
lines = {{0,0,0,0},{0,0,1,1},{0,1,0,1},{0,1,1,0}}

lines[0] = {0,0,0,0} // 노드없음
lines[1] = {0,0,1,1} // 2번 3번과 연결
lines[2] = {0,1,0,1} // 1번 3번과 연결
lines[3] = {0,1,1,0} // 2번 1번과 연결

코드 동작과정은 다음과 같다.

1. 노드와 간선의 개수를 입력받고 lines[][], visited[] 배열을 초기화

2. 연결해야되는 노드끼리 lines[num1][num2] = lines[num2][num1] = 1; 를 통해 연결

3. lines[][] 배열을 순회하며(1부터 시작!) 각노드에 대해 visited[] 배열의 방문 여부를 체크해 방문하지 않았을 경우 탐색 dfs(index) 메서드를 호출한다.

4. dfs(index) 메서드에서는 인자로 들어온 index에 대해 방문여부를 true 로 바꿔준다.

5. lines[parameter-index][for-index] 를 순회하며 현재 노드와 연결된 노드들을 체크한다. 연결값이 1이고, 방문하지 않은 노드일경우 재귀를 통해 다시 dfs(for-index)를 호출한다.

6. 모든노드를 탐색할 경우 1을 리턴한다. (=문제에서 하나의 연결 요소를 모두 탐색)

7. 다시 main() 메서드의 반복문으로 돌아와 리턴값으로 돌아온 1을 결과변수 result에 누적시키고 방문하지 않은 새로운 연결요소가 있는지 체크하여 위 과정을 반복한다.

8. 위 모든 과정이 끝난후 result를 출력하고 종료.