백준 11724번(DFS)

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

import java.net.Inet4Address;
import java.util.*;

public class Main {

static boolean[] visited;
static ArrayList<Integer>[] A;



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

    visited = new boolean[N+1];

    A = new ArrayList[N+1];



    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 1 ; i < N+1; i++)
    {
        A[i] = new ArrayList<>();
    }

    for (int i = 0; i < M; i++)
    {
        st = new StringTokenizer(br.readLine());

        int u = Integer.parseInt(st.nextToken());

        int v = Integer.parseInt(st.nextToken());

    A[u].add(v);
    A[v].add(u);
    }

    int count = 0;

    for (int i = 1; i<= N; i++)
    {
        if(!visited[i])
        {
            count++;
            dfs(i);
        }
    }

    System.out.println(count);











}

public static void dfs(int node)
{
    if(visited[node])
    {
        return;
    }

    visited[node] = true;
    for (int i : A[node]) {
        if(!visited[i])
        {
            dfs(i);
        }
    }
}

}
강의를 보면서 푼 문제이다. DFS유형의 문제는 일단 boolean배열과 ArrayList배열을 Main메서드 밖에다가 먼저 선언해야 한다. 그 후 반복문 안에 ArrayList배열 각각의 값마다 다시 배열을 생성한다. 방향이 정해지지 않고 양방향이면 서로 서로 add를 한다. 그 후 만약 방문을 하지 않았다면 count++을 한 후 그 방문한 곳의 dfs을 실행한다. 이때 dfs는 메서드를 따로 설정해서 문제를 풀어야한다. boolean배열과 ArrayList배열을 이때 사용하기 위해 따로 Main메서드 바깥에다가 설정한 것 같다. 어쨌든 dfs메서드는 만약 이미 방문을 했던 곳이면 그대로 종료한다. 방문하지 않았다면 visited=true로 바꾼 후 그 배열이 가졌던 값중에 방문하지 않은 값을 찾아서 그 값에서 바로 dfs를 실행한다.
이렇게 강의를 이용해서 dfs를 이해하니까 훨씬 귀에 잘 들어오는 것 같다. 정말 좋은 것 같다.