πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.11724 μ—°κ²° μš”μ†Œμ˜ 개수

πŸ“– 문제

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

λ°©ν–₯ μ—†λŠ” κ·Έλž˜ν”„κ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, μ—°κ²° μš”μ†Œ (Connected Component)의 개수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

πŸ” 접근법

BOJ Q.11724 μ—°κ²° μš”μ†Œμ˜ 개수

μ—°κ²° μš”μ†Œμ˜ 개수

즉 λͺ‡κ°œμ˜ μ—°κ²° κ·Έλž˜ν”„κ°€ μžˆλŠ” 지 μž…λ‹ˆλ‹€.

κ°€μ€‘μΉ˜κ°€ μ—†λŠ” κ·Έλž˜ν”„κ°€ μ£Όμ–΄μ§€λ―€λ‘œ BFS / DFS 둜 풀이가 κ°€λŠ₯ν•©λ‹ˆλ‹€.

무방ν–₯κ·Έλž˜ν”„κ°€ μ£Όμ–΄μ§€λ―€λ‘œ μΈμ ‘λ¦¬μŠ€νŠΈλ₯Ό μΆ”κ°€ν•  λ•Œ μ–‘μͺ½μœΌλ‘œ μΆ”κ°€ ν•΄μ€λ‹ˆλ‹€ (u,v) (v,u) μ—°κ²°

κ·Έ ν›„

BFS DFS 탐색을 톡해 μ—°κ²° κ·Έλž˜ν”„μ˜ 개수λ₯Ό ꡬ할 수 μžˆμŠ΅λ‹ˆλ‹€.

πŸ’» μ½”λ“œ

package problem.bfsdfs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_11724 {
    static int N, M, answer;
    static boolean[] visit;
    static List<List<Integer>> adList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        String input[] = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        adList = new ArrayList<>();
        for(int i=0; i<N+1; i++) {
            adList.add(new <Integer>ArrayList());
        }
        visit = new boolean[N + 1];
        for (int i = 0; i < M; i++) {
            String temp[] = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            adList.get(u).add(v);
            adList.get(v).add(u);
        }
        answer = 0;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                dfs(i);
                answer++;
            }
        }
        System.out.println(answer);
        br.close();
    }

    public static void bfs(int num){
        Queue<Integer> queue = new LinkedList<>();
        visit[num] = true;
        queue.add(num);

        while(!queue.isEmpty()){
            int current = queue.poll();
            for (int next : adList.get(current)) {
                if(visit[next]==true){
                    continue;
                }
                visit[next]=true;
                queue.add(next);
            }
        }
    }
    public static void dfs(int num){
        visit[num] = true;
        for(int next : adList.get(num)){
            if(visit[next]){
                continue;
            }
            dfs(next);
        }
    }
}


Written on October 24, 2020