[백준] 11724번. 연결 요소의 개수(JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    static boolean check[];
    static int arr[][];
    static int edge, node;
    static int count = 0;
    public static void main(String[] args) throws IOException {

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

        st = new StringTokenizer(br.readLine());

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

        arr = new int[edge+1][edge+1];
        check = new boolean[edge + 1];

        for (int i = 0; i < node; 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;
        }

        for(int i = 1; i <= edge; i++){
            if(check[i] == false) { // 방문한 적 없는 노드라면 dfs.
                dfs(i);
                count++;
            }
        }

        System.out.println(count);
    }


    public static void dfs(int start) {
        check[start] = true;

        for(int i = 0 ; i <= edge; i++) {
            if(arr[start][i] == 1 && !check[i]) {
                dfs(i);
            }
        }

    }

}

 

연결된 노드를 먼저 인접행렬로 표현한 뒤에 방문한 적이 없는 노드를 기준으로 dfs를 사용하는 것이다.

 

재귀적인 개념이 들어가 있기 때문에 처음 사용해 봐서 어려움이 있었지만 조금 힘들더라도 한 줄씩 직접 숫자를 넣어가며 찾아가는 과정을 통해 이해할 수 있었다.