(C++) - 백준(BOJ) 9372번 : 상근이의 여행

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

unoin find를 이용해 푼 문제였습니다.

 

풀이방법

 1. 생각하기 : 국가의 개수가 n이라면 1 ~ n까지의 국가를 여행해야하기 때문에 국가를 노드로 생각하고 여행하는 경로를 간선이라고 생각해 모든 노드가 연결된, 사이클이 없는 양방향 그래프를 만드는 문제라고 생각할 수 있습니다.

 

 2. union find : parent를 처음에는 다르게 둡니다. find를 이용해 두 국가의 부모가 누구인지 확인합니다. 만약 다르다면 다른 그래프이므로 더 작은 번호의 국가가 큰 번호의 국가의 부모가 되도록 기준을 만들고 union해주면 됩니다.

 

 3. 답 출력 : 한 번 여행한다는 의미는 서로 다른 여행경로 그래프를 합쳐서 하나의 경로를 만든다는 의미입니다. 따라서 union함수가 호출될 때마다 한 번 여행한다고 생각할 수 있습니다. 따라서 해당 개수를 출력하면 됩니다.

Code

#include <iostream>
#include <vector>
using namespace std;
int t;

int find(int a, vector<int> &parent){
    if(a == parent[a]) return a;
    return find(parent[a],parent);
}

void unionParent(int x, int y, vector<int> &parent){
    int a = find(x,parent);
    int b = find(y,parent);
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

int main(){
    cin >> t;
    while(t--){
        int n,m,ans=0;
        cin >> n >> m;
        vector <int> parent(n + 1);
        vector <int> graph[n + 1];

        for(int i = 1; i <= n; i++) parent[i] = i;

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

        for(int i  = 0 ; i < n; i++){
            for(int j = 0; j < graph[i].size(); j++){
                if(find(i,parent) != find(graph[i][j],parent)){
                    unionParent(i,graph[i][j],parent);
                    ans++;
                }
            }
        }

        cout << ans <<'\n';
    }
}