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

문제 링크

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

11724번: 연결 요소의 개수

---

 

 

 

풀이

DFS로 접근했고 딱히 설명할 부분은 없는 것 같다.

굳이 하자면, 연결 요소를 구하는 문제이기 때문에 chk변수를 둬서, 방문하지 않은 곳에 첫 방문 시를 새로운 연결 요소가 있는 경우로 두고 풀었음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BaekJoon11724 {

    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());

        int[][] arr = new int[N+1][N+1];
        boolean[] bl = new boolean[N+1];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            arr[x][y] = arr[y][x] = 1;
        }

        int chk = 0;
        for(int i = 1; i <= N; i ++) {
            if(!bl[i]){
                dfs(arr, bl, i);
                chk++;
            }
        }

        System.out.println(chk);

    }

    private static void dfs(int[][] arr, boolean[] bl, int idx) {

        if(bl[idx]) return;
        bl[idx] = true;

        for(int i = 1; i < arr.length; i++) {
            if(arr[idx][i] == 1 && !bl[i]) {
                dfs(arr, bl, i);
            }
        }

    }

}