Q. 11724 자바 : 연결 요소의 개수

Q. 11724 자바 : 연결 요소의 개수

 

문제 : boj.kr/11724

실버 2 난이도의 문제이다.

 

정점의 수와 간선이 주어졌을 때 연결 요소의 수를 계산하는 문제이다.

풀려고 보니 연결 요소가 뭔지 모르겠어서 찾아봤더니, 

서로 연결된 정점의 집합을 연결 요소로 이해하면 될 것 같다.

주의해야 할 점은 격자형 그래프 + 양방향 그래프이므로 간선(x, y)을 입력받는다면, 

그래프에서는 graph[x][y], graph[y][x] 둘  다 표시를 해야한다.

 

사실 문제를 풀 때 고민했던 내용이 두가지 있었다.

첫번째는 정점의 수 N이 주어진다고는 써있지만,

이후 조건이  1 <= N <= 1000 이라고 되있으므로,

주어진 N보다 정점이 커질 수 있는지에 대한 고민이 있었는데

그냥 N보다 작거나 같은 값만 정점으로 주어진다고 풀었더니 다행히 풀렸다.

두번째는 간선만 주어지므로 격자형 그래프가 아닌, ArrayList를 이용할까 고민해봤는데

 

정점 N, 간선 M이 주어지므로 시간복잡도는 아래와 같다.

1. 정점에 연결된 간선 조회- O(N)

2. DFS, BFS 순회 - O(N^2)

따라서 약 O(N^2) 정도의 시간복잡도를 가진다고 예상할 수 있다.

 

이 문제의 경우 정점의 개수가 최대 1,000개이므로 시간초과는 걱정하지 않아도 된다.

입력값은 두 정점이 연결됬는지만 확인하면 되므로 boolean을 사용해 풀었다.

 

풀이는 아래와 같다.

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static boolean[][] graph;
    static boolean[] visit;

    static int[] dy = new int[]{0, 1, 0, -1};
    static int[] dx = new int[]{1, 0, -1, 0};

    static void input() {

        N = scan.nextInt();
        graph = new boolean[N + 1][N + 1];
        visit = new boolean[N + 1];

        M = scan.nextInt();
        for (int i = 1; i <= M; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            graph[y][x] = true;
            graph[x][y] = true;
        }
    }

    static void dfs(int start) {

        visit[start] = true;
        for (int i = 1; i <= N; i++) {
            if (graph[start][i] && !visit[i]) {
                dfs(i);
//                bfs(i);
            }
        }
    }

    static void bfs(int start) {

        Queue<Integer> que = new LinkedList<>();
        visit[start] = true;
        que.add(start);

        while (!que.isEmpty()) {
            int s = que.poll();
            for (int i = 1; i <= N; i++) {
                if (graph[s][i] && !visit[i]) {
                    que.add(i);
                    visit[i] = true;
                }
            }
        }
    }

    static void pro() {

        int cnt = 0;
        for (int i = 1; i <= N;  i++) {
            if (!visit[i]) {
                bfs(i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {

        input();
        pro();
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}