[JAVA] [그래프] 백준 11724번

[JAVA] 백준 11724번 - 연결 요소의 개수

 

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

public class Main {

    static ArrayList<ArrayList<Integer>> graph; //정점과 간선을 표현할 그래프
    static boolean[] visited;   //방문한 정점 체크를 위한 배열

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        graph = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        visited = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        visited[0] = true;
        int connectedComponentCount = 0;

        for (int i = 0; i < graph.size(); i++) {    //방문한적이 없는 경우 연결요소를 구하고, 연결요소 개수 증가
            if (visited[i] == false) {
                dfs(i);
                connectedComponentCount++;
            }

        }

        bw.write(String.valueOf(connectedComponentCount));
        bw.flush();
        bw.close();
    }

    private static void dfs(int startU) {   //깊이우선탐색을 통해 연결요소를 전부 구함

        visited[startU] = true;
        for (int value : graph.get(startU)) {
            if (visited[value] == false) {
                dfs(value);
            }
        }

    }

}

 

정답을 맞춘 풀이방법

1. ArrayList<ArrayList<Integer>> 를 통해 그래프를 초기화 시키고, 정점과 간선을 입력받음.

2. 방문한 적이 없는 정점의 경우 DFS로 연결요소를 구함.

3. 이미 방문한적이 있는 정점의경우 연결요소를 구하지 않음. 이후 최종 결과 출력함