[알고리즘] 백준_연결 요소의 개수 - 11724

깊이 우선 탐색(DFS)

• 그래프 완전 탐색 기법 중 하나

• 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색 수행

깊이 우선 탐색 핵심 이론

• 인접 리스트로 그래프를 표현하고, 방문 배열 초기화, 시작 노드를 스택에 삽입해준다. 노드를 삽입할 때 해당 위치의 방문 배열을 T로 변경해준다.

• pop하며 노드를 꺼낸 후, 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.

• 방문 배열이 모두 T일 때까지 반복

문제 설명

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

입력

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

출력

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

문제 분석 및 해결 방법

연결 요소는 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 의미한다. 따라서 한 번의 분기가 끝날 때마다 count++를 해주면 된다.

처음에 에지의 양끝 점을 입력 받을 때, 방향이 없는 그래프이므로 양쪽 방향으로 에지를 모두 저장해줘야 한다.

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

public class Main {
    static ArrayList<Integer> [] list;
    static boolean visited [];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int count = 0;

        list = new ArrayList[N+1];
        visited  = new boolean[N+1];

        for(int i=1;i<N+1;i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(bf.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
        for(int i=1;i<N+1;i++){
            if(!visited[i]){
                count++;
                DFS(i);
            }
        }
        bw.write(Integer.toString(count));
        bw.close();
    }
    static void DFS(int v){
        if(visited[v]) return; // 모두 방문했을 때
        visited[v] = true;
        for(int i : list[v]){ // 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행
            if(visited[i]==false) DFS(i);
        }
    }
}

참고 : Do it! 알고리즘 코딩테스트 with JAVA