[해커랭크] Roads and Libraries (C++)

문제 링크: www.hackerrank.com/challenges/torque-and-development/problem

Roads and Libraries | HackerRank

1. 주의할 점

- 범위를 잘 확인한다

- 각 쿼리마다 초기화를 잘 수행한다

- 입력받은 길 중에서, 도서관을 1개 세우는 경우: (Cnt-1)*C_road + C_lib만큼의 비용이 발생하고 각각 도서관을 세우는 경우: Cnt*C_lib만큼의 비용이 발생한다. 즉 C_road>=C_lib일때, 각각 도서관을 세우면 된다

 

2. 구현

- 모든 도로를 V[]벡터에 저장한다

- Flag[] 배열을 1~N까지 확인하면서 아직 어떤 클러스터에도 속하지 못한 경우, BFS를 수행한다(Flag값이 False일 때)

- BFS를 통해 클러스터를 구하고, Result값에 1개의 도서관을 세울 때 발생하는 비용을 더한다. 왜냐하면 BFS를 수행한다는 것은 이미 각각 도서관을 세우는것보다 각 클러스터에 도서관을 1개씩 세우는것이 저렴하기 때문이다

 

#include <bits/stdc++.h>

using namespace std;
bool flag[100001];
vector<int> v[100001];
vector<string> split_string(string);

// Complete the roadsAndLibraries function below.
long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
    long long result=0;
    if(c_road >= c_lib) {
        result = n;
        return c_lib * result;
    }
    for(int i=1;i<=n;i++){
        flag[i]=false;
        v[i].clear();
    }
    
    for(int i=0;i<cities.size();i++){
        int a = cities[i][0];
        int b = cities[i][1];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    for(int i=1;i<=n;i++){
        if(!flag[i]){
            flag[i]=true;
            int cnt=1;         
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int cidx = q.front();
                q.pop();
                for(int k=0;k<v[cidx].size();k++){
                    int next = v[cidx][k];
                    if(!flag[next]){
                        flag[next]=true;
                        cnt++;
                        q.push(next);
                    }
                }
            }
            result+=(cnt-1)*c_road + c_lib;           
        } 
    }
    return result;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string nmC_libC_road_temp;
        getline(cin, nmC_libC_road_temp);

        vector<string> nmC_libC_road = split_string(nmC_libC_road_temp);

        int n = stoi(nmC_libC_road[0]);

        int m = stoi(nmC_libC_road[1]);

        int c_lib = stoi(nmC_libC_road[2]);

        int c_road = stoi(nmC_libC_road[3]);

        vector<vector<int>> cities(m);
        for (int i = 0; i < m; i++) {
            cities[i].resize(2);

            for (int j = 0; j < 2; j++) {
                cin >> cities[i][j];
            }

            cin.ignore(numeric_limits<streamsize>::max(), '\n');
        }

        long result = roadsAndLibraries(n, c_lib, c_road, cities);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}