[백준/Java] 연결 요소의 개수 11724 그래프 탐색(DFS)

 

문제

 

 

 

 

풀이

 

dfs를 이용해 다 돌았는데 방문하지 않은 곳이 있다면 +(플러스)를 해주어 연결 요소의 개수를 더해주었다.

이제서야 dfs에 대해서 점점 이해하게 되는 것 같다.. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static boolean[] visited;
    public static List<Integer>[] graph;
    public static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        visited = new boolean[N + 1];
        graph = new ArrayList[N + 1];

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

        for (int i = 0; i < K; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }
        
        for (int i = 1; i < N + 1; i++) {
            // 연결 되어있지 않을 때 +를 해준다.
            if (!visited[i]) {
                answer++;
                dfs(i);
            }
        }

        System.out.println(answer);
    }

    // 깊이 우선 탐색으로 검사 
    public static void dfs(int num) {
        visited[num] = true;

        for (int i = 0; i < graph[num].size(); i++) {
            if (!visited[graph[num].get(i)]) {
                dfs(graph[num].get(i));
            }
        }
    }
}

 

 

 

정답