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

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

 

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

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

---

1.  아이디어

 

주어진 입력으로 만들어질 수 있는 그래프의 개수를 구하는 문제로 BFS, DFS, Union-Find 알고리즘 3가지 방법으로 해결할 수 있었다.

---

2. 문제풀이

 

BFS와 DFS는 주어진 입력으로 그래프의 연결관계를 나타내는 인접리스트와 각 정점을 방문했는지 표시하는 방문 체크 배열을 만든 후 반복문으로 각 정점을 순회하며 방문한 정점이면 넘어가고 방문하지 않은 정점이면 탐색으로 그래프의 개수를 세는 방식으로 구현했다. Union-Find는 인접리스트를 만드는 대신 바로 집합 연결을 해주었다. 이후 각 정점이 집합의 그룹장인지 여부만 세면 간단하게 그래프의 개수를 구할 수 있다.

---

3. 코드

 

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

public class Main_BFS {
    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());
        int M = Integer.parseInt(st.nextToken());

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

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

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

        boolean[] visited = new boolean[1 + N];
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (visited[i]) continue;

            bfs(i, adj, visited);
            cnt++;
        }

        System.out.println(cnt);
    }

    private static void bfs(int start, List<List<Integer>> adj, boolean[] visited) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);

        visited[start] = true;

        while (!q.isEmpty()) {
            int node = q.poll();

            for (int next : adj.get(node)) {
                if (visited[next]) continue;

                q.offer(next);
                visited[next] = true;
            }
        }
    }

}

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

public class Main_DFS {
    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());
        int M = Integer.parseInt(st.nextToken());

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

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

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

        boolean[] visited = new boolean[1 + N];
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (visited[i]) continue;

            dfs(i, adj, visited);
            cnt++;
        }

        System.out.println(cnt);
    }

    private static void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;

        for (int next : adj.get(node)) {
            if (visited[next]) continue;

            dfs(next, adj, visited);
        }
    }

}

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

public class Main_Union_Find {

    private static int[] p;

    private static int[] make(int N) {
        int[] arr = new int[1 + N];
        for (int i = 1; i <= N; i++) arr[i] = i;
        return arr;
    }

    private static int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }

    private static void union(int x, int y) {
        p[find(y)] = find(x);
    }

    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());
        int M = Integer.parseInt(st.nextToken());

        p = make(N);

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

            union(u, v);
        }

        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (i == p[i]) cnt++;
        }

        System.out.println(cnt);
    }
}

---

4. 후기

 

- BFS

- DFS

- Union-Find