백준 연결요소의 개수 11724

2020-10-21

1. 백준 연결요소의 개수 11724 문제

1.1. 문제

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

1.2. 입력

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

1.3. 출력

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

1.4. 예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

1.5. 예제 출력 1

1.6. 예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

1.7. 예제 출력 2

3. 컴퓨팅적 사고

그래프 상에서 연결요소의 개수를 구하는 문제입니다. 여기서 가장 중요한점은 각각의 그래프를 연결 요소라고 하는데 나누어진 그래프의 개수를 찾는 문제입니다.

연결요소의 개수를 찾기전에 그래프 개념에 대해서 살펴보고 넘어가겠습니다.
그래프 인접행렬, 인접리스트 및 DFS,BFS 해당 포스트에서 인접행렬, 인접리스트와 DFS,BFS의 개념에 대해서 상세히 설명해놓았습니다. 이부분을 참고하시면 어렵지 않게 문제를 푸실 수 있을것 입니다.

문제를 풀기위해서는 필요한 지식은 다음과 같습니다.

인접행렬과 인접리스트의 차이를 알 수 있어야합니다.
DFS와 BFS의 차이점을 알고 있어야합니다.
가장 적은 정점부터 방문해야한다는 조건이 있을때는Sort를 진행해야합니다.
DFS, BFS 백준 1260번 문제와 유사하므로 이것이 잘 이해가 가지않으신다면 먼저 풀어보시는것을 권장드립니다.
직접 손으로 그래프를 그리면서 하나하나씩 과정이 어떻게 이루어지는지 알고 계셔야합니다.

간략히 풀이한 것에 말씀드려보면 (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)이라는 조건이 있으므로 각각의 ArrayList<ArrayList<Integer>> 형식의 리스트에 값을 할당하였습니다. 또한, 내가 체크한 부분인지 아닌지를 확인하기 위한 check변수를 선언하여 문제를 해결 하였습니다.
결국, check된 부분이 false인 경우에 카운트 값을 하나씩 올려주면서 재귀호출을 하게 된다면 결국엔 그 정점(V)에 포함된 간선(E)의 연결요소의 개수를 알 수 있겠죠?

시간복잡도

시간복잡도는 현재 (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 의 조건을 가지고 있습니다.
N은 최대 1000까지의 수를 가질 수 있으며, M 같은경우는 (1000*(999-1)/2) 까지의 값을 가집니다.
약 500,000 정확히 말해서 499,500까지의 값을 가질 수 있다는 말인데요.

N의 시간복잡도에 대해서는 O(N^2)까지의 수를 계산 하였을때, 1000 * 1000 => 1,000,000 백만까지 나오게 됩니다. M같은경우는 O(M^2) 약 500,000 이기때문에 O(M^2)을 하게 되면 500,000 * 500,000 => 250,000,000,000 = 2500억정도의 시간복잡도가 계산 될 수 있기때문에 주의하여야합니다. 시간복잡도는 약 1초에 1억번 컴퓨터가 수행 할 수 있는 시간을 말하는데요. 2500억정도가 나오게된다면 컴퓨터 시간복잡도를 수행하는데 있어서 2500초 정도가 걸린다고 생각하시면 됩니다. 이러한 시간복잡도 또한 무시할 수 없는 알고리즘의 하나이기 때문에 주의를 귀울이셔야 할 것 같습니다.

4. 소스코드

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

/*
BFS DFS두가지 방법으로 사용하기
 */
public class 연결요소11724 {
    static int n;
    static int m;
    static boolean[] connCheck;
    static boolean[] check;
    static ArrayList<ArrayList<Integer>> A = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<=n; i++){
            A.add(new ArrayList<Integer>());
        }
        check = new boolean[n+1];

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            A.get(x).add(y);
            A.get(y).add(x);
        }

        int answer = 0;
        for(int i=1; i<=n; i++){
            if(!check[i]){
                //dfs(i);
                bfs(i);
                answer++;
            }
        }
        System.out.println(answer);
    }

    private static void bfs(int v) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        check[v] = true;

        while(!q.isEmpty()){
            int x = q.poll();
            for(int i=0; i<A.get(x).size(); i++){
                int y = A.get(x).get(i);
                if(!check[y]){
                    check[y] = true;
                    q.offer(y);
                }
            }
        }
    }

    private static void dfs(int x) {
        check[x] = true;
        for(int i=0; i<A.get(x).size(); i++){
            int y = A.get(x).get(i);
            if(!check[y]){
                check[y] = true;
                dfs(y);
            }
        }
    }
}

AlgorithmBOJ