[BOJ_11724] 연결요소 (java)

문제링크

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

11724번: 연결 요소의 개수

문제설명

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

제한사항

제한시간	메모리제한
3초	512MB

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
DFS, BFS를 사용해서 해결하자.

연결요소 2개

연결요소는 그래프가 연결되어 있는 요소들을 의미합니다. 위 그림을 보면 그래프가 2개라고 표현할 수도 있지만 이것은 연결요소가 2개라고도 표현할 수 있습니다. 그래프의 연결된 모든 정점을 한번씩만 탐색해보는 그리디 알고리즘은 BFS와 DFS를 사용하면 연결되어있는 모든 정점에 대하여 확인할 수 있습니다. 따라서 모든 정점을 돌며 DFS 혹은 BFS로 체크가 되어 있지 않다면 그와 연결된 모든 연결요소를 체크하여주면서 연결요소의 수를 간단히 구할 수 있습니다.

 

저는 문제를 해결하기 위해 dfs를 사용하였습니다. 아래 구현코드를 참고하여 확인해주시면 감사하겠습니다.

 

구현코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int vertexSize = sc.nextInt();
        int edgeSize = sc.nextInt();

        ArrayList<Integer>[] edgeList = new ArrayList[vertexSize+1];
        for(int i = 1; i <= vertexSize; i++)
            edgeList[i] = new ArrayList<Integer>();

        for(int i = 0; i < edgeSize; i++){
            int firstVertex = sc.nextInt();
            int secondVertex = sc.nextInt();

            edgeList[firstVertex].add(secondVertex);
            edgeList[secondVertex].add(firstVertex);
        }

        boolean[] checked = new boolean[vertexSize+1];
        int count = 0;
        for(int i = 1; i <= vertexSize; i++){
            if(!checked[i]){
                dfs(i,checked,edgeList);
                count += 1;
            }
        }
        System.out.println(count);
    }

    public static void dfs(int x, boolean[] checked, ArrayList<Integer>[] edgeList){
        checked[x] = true;
        ArrayList<Integer> vertexs = edgeList[x];
        for(int i = 0; i < vertexs.size(); i++){
            int ver =vertexs.get(i);
            if(!checked[ver])
                dfs(ver,checked,edgeList);
        }
    }
}

 

시간복잡도

간선을 인접리스트로 구현하였으며 DFS 혹은 BFS는 모든 정점에 대하여 한번씩 수행되므로 V(정점의 개수)가 걸리며, 반복문으로 연결되어있는 정점을 확인하는데 이는 E(간선의 수)만큼 확인하게 됩니다.

따라서 시간 복잡도는 $O(V+E)$가 됩니다.