[java] 백준 11724번 문제(연결 요소의 개수)

원본 링크 : https://www.acmicpc.net/problem/11724

---

문제설명

 

 

소스코드

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

public class Boj_11724
{
    static ArrayList<Integer>[] adjacencyList; // 인접 리스트
    static boolean[] visited; // 방문 체크

    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()); // 엣지 개수

        adjacencyList = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for(int i = 1; i < n + 1; ++i) adjacencyList[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());
            adjacencyList[u].add(v); // 인접 리스트에 추가
            adjacencyList[v].add(u); // 인접 리스트에 추가
        }

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

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

 

설명

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

 

그래프를 인접 리스트로 저장하고 방문 배열도 초기화한다.

방향이 없는 그래프이기 때문에 양쪽 방향으로 엣지를 모두 저장한다.

 

임의의 시작점에서 DFS를 수행한다.

현재의 경우 1을 시작점으로 정하고 탐색을 마친 이후 방문한 곳은 1, 2, 5가 되었다.

 

아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행한다.

현재의 경우 3, 4, 6 순서로 탐색을 마쳤고, 모든 노드를 방문했으니 전체 탐색을 종료한다.

 

이 과정들을 통해 총 2번의 DFS가 진행되었다는 것을 알 수 있다.

즉, 연결 요소 개수는 2개이다.