백준 2606번

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

import java.util.*;

public class Main {

static boolean[] visited;      // 클래스 레벨 변수 → dfs에서 사용 가능
static ArrayList<Integer>[] graph;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int computerCount = Integer.parseInt(br.readLine());
    int connectComputer = Integer.parseInt(br.readLine());

   graph = new ArrayList[computerCount+1];
    visited = new boolean[computerCount+1];

    for (int i = 1 ; i <= computerCount; i++)
    {
        graph[i] = new ArrayList<>();
    }



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

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

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

    graph[first].add(second);
    graph[second].add(first);

}

dfs(1);

int count = 0 ;
for (int i = 2 ; i <= computerCount;i++)
{
    if(visited[i])
    {
        count++;
    }
}

    System.out.println(count);









}

// graph[1] = 2,5 dfs(2)
static void dfs(int node){
visited[node] = true;
for (int next : graph[node]) {
if (!visited[next])
{dfs(next);}
}

}

}

이번 문제에서 DFS란걸 배웠는데 dfs 메서드를 보니 정말 감탄만 나왔다. 또한 ArrayList와 boolean을 메인 메서드 이전에 선언하여 dfs메서드를 선언한 것과 ArrayList에 있는 graph를 또 ArrayList를 선언한 게 놀라웠다. 그리고 graph[first].add(second) , graph[second].add(first)를 이용하여 양방향 연결 저장을 한것도 정말 놀라웠다. dfs 이해하는데만 30분이 걸렸다. 확실히 이제 유명한 알고리즘이어서 그런지 어렵다.