[백준] 11724 연결 요소의 개수(Silver.2) - DFS

문제

코드

연결 요소(연결된 컴포넌트(서브그래프)) 찾기 유형의 문제다.

DFS를 이용하여 서브 그래프를 찾아내고 찾아낸 서브 그래프의 개수를 출력하는 간단한 문제이다.

같은 유형의 문제(유기농 배추)

• 풀이 방법

1. 아래 사진과 같이 LinkedList<Integer>[]로 노드를 만들고 연결 리스트 형태로 그래프를 구현한다.
   

   

2. 방문하지 않은 노드에 대해 dfs를 실행하여 서브 그래프 개수를 카운팅한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class _11724 {
    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()); // 정점(Node)의 개수
        int M = Integer.parseInt(st.nextToken()); // 간선(Edge)의 개수

        // ---------- 1 ----------
        LinkedList<Integer>[] list = new LinkedList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new LinkedList<>();
        }
        boolean[] visited = new boolean[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 무방향 그래프일 경우 양방향 간선 처리를 해야 함 
            list[a].add(b);
            list[b].add(a);
        }

        // ---------- 2 ----------
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (!visited[i]){
                dfs(list, visited, i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static void dfs(LinkedList<Integer>[] list, boolean[] visited, int nowIdx) {
        visited[nowIdx] = true;

        for (int neighbor : list[nowIdx]) {
            if (!visited[neighbor])
                dfs(list, visited, neighbor);
        }
    }
}