ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

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

 

11724๋ฒˆ: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜

์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ u, v ≤ N, u ≠ v) ๊ฐ™์€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ๋งŒ ์ฃผ

www.acmicpc.net

์ดํ•ด

๋ฌธ์ œ ํ’€์ด์— ์•ž์„œ ๋ฌธ์ œ๋ฅผ ์ดํ•ดํ•ด๋ณด์ž.

  • ์—ฐ๊ฒฐ ์š”์†Œ(Connected Component)๋Š” ์—ฐ๊ฒฐ๋œ ์ •์ ์˜ ์ง‘ํ•ฉ์„ ์˜๋ฏธํ•œ๋‹ค. ๋‹ค์Œ ์ด๋ฏธ์ง€์—์„œ์˜ ์—ฐ๊ฒฐ ์š”์†Œ๋Š” 4๊ฐœ์ด๋‹ค.
  • ๋”ฐ๋ผ์„œ ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์„ ํ†ตํ•ด ์—ฐ๊ฒฐ๋œ ์ •์ ์„ ๋ชจ๋‘ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•˜๊ณ 
  • ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ ๋˜์ง€ ์•Š์€ ์ •์ ์ด ๋ฐœ๊ฒฌ๋˜๋ฉด ์ƒˆ๋กœ์šด ์—ฐ๊ฒฐ ์š”์†Œ์ž„์„ ์˜๋ฏธํ•œ๋‹ค.

https://www.mathworks.com/matlabcentral/fileexchange/46457-splitting-a-network-into-connected-components

ํ’€์ด

  • ์ „์ฒด ๋…ธ๋“œ(1~N)๋ฅผ ์ˆœํšŒํ•˜๋ฉฐ ํ•ด๋‹น ๋…ธ๋“œ๊ฐ€ ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์•˜๋‹ค๋ฉด, ์—ฐ๊ฒฐ ์š”์†Œ(result)๋ฅผ ์นด์šดํŠธํ•œ๋‹ค.
  • ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ์‹œ์ž‘์œผ๋กœ ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰(BFS or DFS)์„ ์ง„ํ–‰ํ•˜๋ฉฐ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•œ๋‹ค.(์ด ๊ธ€์—์„  BFS๋ฅผ ๊ตฌํ˜„ํ–ˆ๋‹ค)
  • ์ฃผ์˜* ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ๋ฅผ ๋ฐœ๊ฒฌ๊ณผ ๋™์‹œ์— ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•˜์ง€ ์•Š์œผ๋ฉด ๋ฌดํ•œ๋ฃจํ”„์— ๋น ์งˆ ์ˆ˜ ์žˆ์œผ๋‹ˆ ์ฃผ์˜ํ•˜์ž.

์ฝ”๋“œ

package BOJ;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ์—ฐ๊ฒฐ_์š”์†Œ์˜_๊ฐœ์ˆ˜_11724 {

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

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        final int N = Integer.parseInt(input[0]);
        final int M = Integer.parseInt(input[1]);
        boolean[] visited = new boolean[N + 1];
        int result = 0;

        List<List<Integer>> graph = new ArrayList<>();

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

        for (int i = 0; i < M; i++) {
            String[] connectInfo = br.readLine().split(" ");
            int u = Integer.parseInt(connectInfo[0]);
            int v = Integer.parseInt(connectInfo[1]);

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


        for (int i = 1; i <= N; i++) {
            if (visited[i]) {
                continue;
            }

            result += 1;

            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);

            while (!queue.isEmpty()) {
                Integer current = queue.poll();
                visited[current] = true;

                for (Integer node : graph.get(current)) {
                    if (!visited[node]) {
                        visited[node] = true;
                        queue.add(node);
                    }
                }
            }
        }


        bw.write(Integer.toString(result));

        bw.close();
        br.close();
    }
}
๋ฐ˜์‘ํ˜•