백준/11724번/Java - 연결 요소의 개수 (DFS)

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

11724번: 연결 요소의 개수

---

연결 요소 (Connected Component)의 개수를 구하는 문제.

 

문제에서는 정점의 개수 N과 정점을 잇는 간선의 개수 M, 각 간선의 양 끝점 u, v가 주어진다.

즉 각 노드와 노드의 위치, 이를 잇는 간선을 알려준 것이다.

 

예제를 따라서 그림을 그려보면 

1-2-5가 연결되어있고, 3-4-6이 연결되어 있다는 것을 알 수 있다.

즉 2개의 연결 요소가 있는 셈이다.

 

특정 노드에서 시작해 그래프 전체를 완전히 탐색하여 더 이상 탐색이 불가능한 경우(탐색이 종료된 경우) 한 개의 연결 요소를 발견할 수 있다.

따라서 탐색이 종료 될때마다 연결 요소의 개수를 + 1 해주면 된다.

 

주어진 조건을 그래프로 나타내기 위해 인접리스트를 활용해서 쉽게 표현할 수 있다.

 

노드의 개수가 N개 이므로 길이가 N인 배열을 선언한다.

배열에는 N번째 노드가 연결된 다른 노드들의 번호를 저장하고 있는 리스트를 담아준다.

 

i번 노드에서 시작하는 경우

 

i번 노드에 방문한다.

i번 노드에 방문한적이 없을 경우,

i번 노드에 연결된 다른 노드(j,k...)들을 차례로 탐색한다.

연결된 노드 중 더 이상 방문한 적 없는 노드가 없을 경우 탐색을 종료한다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] arr;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        //배열 초기화
        for(int i=1; i<=N; i++) {
            arr[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());
            arr[u].add(v);
            arr[v].add(u);
        }

        //1에서 출발하는 경우부터 탐색.
        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                dfs(i);
                count++; //탐색이 종료되었을 경우 count++
            }
        }

        System.out.println(count);
        br.close();
        bw.flush();
        bw.close();
    }

    private static void dfs(int idx) {
        if(visited[idx]) {
            return;
        }

        visited[idx] = true;
        for(int i : arr[idx]) {
            //arr[idx] 노드에 연결된 다른 노드들을 탐색(단 방문한 적 없을 시)
            if(!visited[i]) {
                dfs(i);
            }
        }
    }
}