백준_11724번_연결 요소의 개수_자바

백준_11724번_연결 요소의 개수_자바

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

11724번: 연결 요소의 개수

 

해당 문제는 그래프 문제이며, DFS와 BFS로 모두 풀이해보았습니다.

 

간선을 저장할 배열과 정점을 저장할 체크 배열을 만든후에 풀이 하시면 되며, 

포인트는 양방향(방향이없는) 간선일때 양쪽 모두 저장해주는것입니다.

ex ) arr[a][b] = arr[b][a] = 1;

 

 

 

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

public class Main {

    static int[][] arr;
    static int[] chx;
    static int node;
    static int edge;
    static int cnt;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        arr = new int[node+1][node+1];
        chx = new int[node+1];

        for (int i = 1; i <= edge; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }

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

    }

    private static void dfs(int x) {
        if(chx[x]==1){
            return;
        }else {
            chx[x]=1;
            for (int i = 1; i <= node; i++) {
                if(arr[x][i] == 1 ){
                    dfs(i);
                }
            }
        }
    }

    private static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        chx[x] = 1;
        while (!q.isEmpty()){
            Integer nowX = q.poll();
            for (int i = 1; i <= node; i++) {
                if(arr[nowX][i]==1 && chx[i]==0){
                    chx[i]=1;
                    q.add(i);
                }
            }
        }
    }

}