[구름 IDE] 비타알고 시즌3 백신(★3)

 

 

문제

 

 

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
constexpr int MAX_N = 200001;
using graph_t = std::vector<int>;
using node_count_t = std::vector<size_t>;
 
int Find(int value, graph_t& g) {
 
    if (g[value] == value)
        return value;
    else
        return g[value] = Find(g[value], g);
 
}
 
void Union(int lhs, int rhs, graph_t& g) {
 
    int lhs_parents = Find(lhs, g);
    int rhs_parents = Find(rhs, g);
 
    if (lhs_parents < rhs_parents) {
        g[rhs_parents] = lhs_parents;
    }
    else {
        g[lhs_parents] = rhs_parents;
    
    }
}
void CheckMaxNode(node_count_t& count_array, graph_t& g) {
 
    //노드의 집합에서 부모 노드들을 찾는다.
    for (const auto& i : g) {
        int parents = Find(i, g);
        //해당 부모노드의 index값을 증가시킨다.
        count_array[parents]++;
    }
    //가장 큰 값을 가진 반복자를 찾는다.
    auto iter = std::max_element(count_array.begin(), count_array.end());
    int index = iter - count_array.begin();
    std::cout << index << " " << *iter<<"\n";
}
 
 
void MakeSet(graph_t& g, int N) {
    //Initlization
    for (int i = 1; i <= N; ++i)
        g[i] = i;
}
 
int main() {
    int N{}, M{}, from_v{}, to_v{};
    std::cin >> N >> M;
 
    graph_t g(N + 1);
    node_count_t count_array(N + 1, 0);
    MakeSet(g, N);
 
    for (int i = 0; i < M; ++i) {
        std::cin >> from_v >> to_v;
        Union(from_v, to_v, g);
    }
    CheckMaxNode(count_array,g);
 
}

 

후기

 

이 문제를 해결하기 위한 키워드는 2가지이다.

 

1. Union-Find 알고리즘을 사용하여 중복이 없는 집합을 생성한다.

    Union() 메서드와 Find() 메서드를 작성하여 해당 알고리즘을 구현하였으며 Find() 알고리즘은 탐색과정의 노드들을

    마지막 root 노드에 붙일 수 있는 최적화 연산을 진행(이를 진행하지 않을 경우 연결 리스트 형태로 변할 수 있다.)

 

2. 치료할 수 있는 환자의 수 와 환자의 번호를 출력한다.

    해당 문제의 해결은 CheckMaxNode()메소드에 작성을 하였으며 처음에는 부모 노드의 개수를 파악해서 체크를 하려고 했지만 Find 과정에서 root노드에 붙지 않는 경우가 생겨서 선형 탐색을 진행하였다. 

 

처음에는 BFS 혹은 DFS를 생각했지만 구현하다 보니 해당 집합의 개수를 파악하기에는 Union-FInd가 더 적합하다고 생각해서 이 방식으로 고치고 구현을 진행하였다.

제한시간이 따로 없어서 문제는 없었지만 노드의 개수가 많아진다면 CheckMaxNode()에서 그만큼 시간이 오래 걸리기 때문에 개선이 필요하다고 생각한다.

 

출처 및 레퍼런스

위클리 비타알고 시즌3 강의 링크: https://edu.goorm.io/learn/lecture/18444/프리미엄-알고리즘-위클리-비타 알고-시즌3

 

 

* 해당 강의는 작성일 기준으로 무료이지만 추후 유료로 전환될 가능성이 있으므로 시즌2 글쓰기와 동일한 방식으로

'테스트 케이스', ' 해설 내용'은 공유하지 않고 게시하였습니다. 그래도 게시글에 문제가 있는 경우 알려주시면 수정하겠습니다.

 

관련 글

[백준] 1717번 집합의 표현

[자료구조 알고리즘/탐색 알고리즘] - 합집합 찾기(Union-Find)