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

백준 - 연결 요소의 개수

내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;


public class baekjoon_11724 {

    static int N, M;
    static boolean[] visited;
    static List<Integer>[] graph; //리스트들을 담는 배열

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);
        graph = new ArrayList[N+1];
        visited = new boolean[N + 1];

        for (int i = 0; i < graph.length; i++) { //배열 초기화 안해주면 에러 난다
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            graph[a].add(b);
            graph[b].add(a);
        }

        int ans = 0;
        for (int i = 1; i < visited.length; i++) {
            if (!visited[i]) {
                ans += 1;
                dfs(i);
            }
        }
        System.out.println(ans);
    }

    private static void dfs(int start) {
        visited[start] = true;
        for (int i = 0; i < graph[start].size(); i++) {
            if (!visited[graph[start].get(i)]) {
                dfs(graph[start].get(i));
            }
        }
    }
}

본질적으로 백준 - 섬의 개수 문제와 동일하다.

그래프를 코드로 나타내는데 두 가지 방법이 있는데 하나는 이차원 배열을 사용하는 것이고 하나는 리스트를 담는 배열을 이용하는 것이다. 리스트를 담는 배열을 만드는 것에도 익숙해지자.

static List<Integer>[] graph; //리스트들을 담는 배열