BOJ) 11724 - 연결 요소의 개수

dfs 로 순열 문제만 풀다가 그래프 들어가니까 방식의 차이때문에 재귀함수에 대해서 제대로 이해했는지에 대한 의문이 들기시작한다 .. 구분 잘하고 더 공부해보자

풀이

리스트배열 연결 노드들을 입력하고, dfs를 통해 start 노드가 연결되어 있는 노드들을 다 방문하고, 아직 방문이 안된 노드가 있으면 for문을 통해 다시 도는데 그때마다 answer값을 추가해주면 된다.

package study;

import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B_11724 {
    static boolean [] visited;
    static ArrayList<Integer> [] arr;
    static int N, M;
    static int answer = 0;;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i = 1; i < N+1; i++) {
            arr[i] = new ArrayList<Integer>();
        }
        int a,b;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            arr[a].add(b);
            arr[b].add(a);
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]){
                dfs(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
    public static void dfs(int start){
        visited[start] = true;
        for(int i : arr[start]){
            if (!visited[i]){
                dfs(i);
            }
        }
    }
}