[BOJ] 11724번 - 연결 요소의 개수

황규빈·2021년 12월 24일
0

알고리즘

목록 보기
2/33

💎 문제


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

💎 입력


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

💎 출력


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

💎 풀이 방법


2학년 때 자료구조 시간에 배웠던 노드간의 연결 부분을 생각하고 풀었다. 따라서 어렵지 않게 풀 수 있었던 것 같다.

그래프 탐색을 이용한 문제로 하나의 정점에서 다른 정점으로 차례차례 이동하는 탐색을 이용하였다. 이 때 DFS(깊이 우선 탐색)을 이용하여 현재 탐색하고 있는 정점과 이어진 정점들을 탐색해서 이어지지 않는 곳까지 차례대로 끝까지 탐색하는 것을 이용한다. 따라서 예를 들어, 정점 0이 1,2와 이어져 있다면 1을 먼저 방문한 뒤 1에 이어진 정점들을 확인하고 탐색이 완료되면 2를 다시 탐색해서 정점 0과 이어진 모든 정점들을 탐색한 뒤 확인하려는 다음 정점으로 이동하는 방식이다.

DFS와 함께 사용하는 그래프 탐색으로 BFS(너비 우선 탐색)방식이 있는데 이는 다음에 사용하는 알고리즘 문제를 풀 때 개념을 작성해보도록 하겠다!

이러한 DFS를 사용하게 되면 두가지를 생각해보아야할 것 같다.
첫 번째는 문제에서 입력된 주어진 정점과 연결된 정점들을 확인하는 배열
두 번째는 그러한 정점을 방문하였다는 확인을 하는 검사가 필요하다는 것이다.

for(int i = 0;i < M;i++){
        cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
}

입력 받은 간선들을 먼저 vector를 이용하여 각 정점에 연결된 정점들을 담아준다. 연결요소를 확인하기 위해서 V[정점]에 연결된 정점들을 차례대로 확인해줄 것이며 이를 아까 설명한 DFS를 사용하였다.

DFS를 사용할 때 백트래킹을 이용하는데 정점에 연결된 부분을 계속해서 찾아가고 만약 더 이상 정점이 찾아지지 않다면 이 정점은 확인하였다는 check를 해준 뒤 다시 되돌아가면 처음 정점과 이어진 정점들을 다시 DFS를 이용하여 찾아갈 것이다.

void dfs(int T){
    check[T] = true;
    for(int i = 0;i < V[T].size();i++){
        if(check[V[T][i]] == false){
            dfs(V[T][i]);
        }
    }
}

위와 같이 check를 이용하여 현재 찾고 있는 정점을 탐색하였다는 표시를 해둔 뒤 정점에 해당하는 연결된 정점들을 모두 찾아낸 뒤 그 정점들 또한 check를 한다. 이러한 처음 dfs함수에 들어가는 정점은 check 되지 않았다면 dfs함수를 실행하는 것으로 코드를 구성하였다.

💎 전체 코드


#include <iostream>
#include <vector>
using namespace std;
vector <int> V[1001];
vector <bool> check(1001);
int N, M;

void dfs(int T){
    check[T] = true;
    for(int i = 0;i < V[T].size();i++){
        if(check[V[T][i]] == false){
            dfs(V[T][i]);
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int u, v;
    int result = 0;
    cin >> N >> M;
    
    for(int i = 0;i < M;i++){
        cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
    }
    
    for(int i = 1;i <= N;i++){
        if(check[i] == false){
            dfs(i);
            result++;
        }
    }
    
    cout << result << "\n";
    
    return 0;
}

💎 고민


근데 이 문제는 그래프 탐색 중에서도 쉬운 문제였던 것 같다. 수업시간에 배웠던 예제 그대로의 내용이였기 때문에 DFS를 이용하기도 쉬웠다. 주로 그래프탐색을 이용할 때에는 DFS를 사용하는 것이 좋을지 BFS를 사용하는 것이 좋을지 확인하고 시간복잡도의 영향이 없다면 DFS를 활용하여 쉽게 구하면 될 것 같다. BFS는 문제의 시간복잡도를 고려할 때 최대한 사용할 수 있도록 하자!

그리고 그래프 탐색하는 문제들은 주로 정점과 같이 입력 값들이 여러개인 것을 확인하고 백트래킹을 이용하여 순차적으로 탐색을 한다는 점에서 알고리즘을 작성하고 어떤 식으로 정점을 확인했는지 check하는 방식과 이어지는 연결 부분을 어떻게 확인할지 알고리즘을 구성해야겠다.

화팅!

profile
안녕하세욤

0개의 댓글