[JAVA] 백준 11724 깊이 우선 탐색(DFS)

 

 

 

 

11724번: 연결 요소의 개수

문제

정점의 개수 N과 간선의 개수 M이 주어지고

간선이 연결된 정점 2개를 M개 주어진다.

몇 개의 연결 요소가 생기는 지 구하시오.

풀이

노드와 무방향 간선이 주어졌을 때 몇 개의 연결 요소가 만들어지는지 구하는 문제이다.

무방향 그래프이므로 간선의 양 쪽 모두를 담아 두어도 된다.

모든 List를 돌면서 해당 정점과 연결된 모든 정점을 방문하면서 Visit를 체크한다.

for(int i=1; i<N; i++){
    // 현재 정점이 방문되지 않은 경우에만 DFS 실행
    if(V[i]){
        // 만약 DFS가 한번에 끝나지 않았다면 연결되지 않은 새로운 연결 요소가 존재
        answer++;
        DFS(i);
    }
}

현재 정점이 방문되지 않았다면 방문을 체크하고 현재 정점과 연결된 모든 정점을 DFS 재귀로 탐색한다.

public static void DFS(int num){
    if(V[num]) return;

    V[num] = true;
    // 정점과 연결된 모든 정점을 방문한다.
    for(int x : A[num]){
        // 연결된 정점이 방문되지 않았다면
        if(!V[x])
            DFS(x);
    } 
}

전체 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static ArrayList<Integer>[] A;
    static boolean[] V;
    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())+1;
        int M = Integer.parseInt(st.nextToken());

        A = new ArrayList[N];
        V = new boolean[N];
        for(int i=0; i<N; i++){
            A[i] = new ArrayList<>();
        }

        for(int i=1; i<M+1; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }

        int answer= 0;
        for(int i = 1; i<N; i++){
            if(!V[i]){
                answer++;
                DFS(i);
            }
        }
        System.out.println(answer);
    }
    public static void DFS(int x){
        if(V[x]) return;

        V[x] = true;
        for(int z : A[x]){
            if(!V[z])
                DFS(z);
        }
    }
}

결과