백준 11724번 : 연결 요소의 개수 [Java]

문제 링크

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제 설명

코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean[] visited;
    static List<Integer>[] A;
    
    public static void main(String[] args) throws Exception{
        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];   //0번 인덱스 미사용
        A = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            A[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            //양방향 그래프이기 때문에 어느 방향이든 사용 가능하게 더해준다.
            A[s].add(e);
            A[e].add(s);
        }

        int cnt = 0;
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                cnt++;
                DFS(i);
            }
        }
        System.out.println(cnt);
    }

    private static void DFS(int v) {
        if (visited[v]) {
            return;
        }

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

풀이

해당 문제는 DFS 문제와 동시에 그래프 구현 문제이다.

 

노드의 최대 개수가 1000이므로 시간 복잡도 N^2 이하의 알고리즘을 사용 가능하다

방문 배열 'v'를 통해 재귀를 하면서 현재 노드와 직/간접적 연결이 있는 노드는 방문처리한다.

방문하지 않는 노드가 있는 경우 for문에서 별도의 dfs를 통해 재귀를 수행한다.