[JAVA] 백준 11724번 - 연결 요소의 개수

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

11724번: 연결 요소의 개수

---

각 노드가 몇 개나 연결되었는지 구하면 되는 문제다

그래서 난 DFS를 활용해서 풀었다

약간 고민했던 점은 dfs를 호출할 떄마다 answer++ 를 하면 각각 나눠진 영역의 개수를 구하게 된다

그래서 연결된 요소들의 개수를 구하기 위해 dfs가 호출되고 visited의 수가 바뀔때마다 answer를 증가해야할 줄 알았는데?!

아니었네..

그냥 호출될 때마다 answer를 키워주면 된다

쉽..쉽네..

아래는 코드!

 

 

자바 코드)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static boolean[] visited;
    static List<List<Integer>> arr = new ArrayList<>();
    static Integer answer;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        answer = 0;

        visited = new boolean[n+1];

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

        for(int i=0;i<m;i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            arr.get(a).add(b);
            arr.get(b).add(a);
        }
        for(int i=1;i<=n;i++) {
            if(!visited[i]) {
                dfs(i);
                answer++;
            }
        }
        System.out.println(answer);
    }

    static public void dfs(int x) {
        visited[x] = true;
        for(int num : arr.get(x)) {
            if(!visited[num]) {
                dfs(num);
            }
        }
    }
}