백준 1976 - 여행가자

https://www.acmicpc.net/problem/1976

 

최대 200개의 도시 수가 인접행렬 형태로 주어진다.

 

문제에서 주어진 여행지들을 모두 여행할 수 있는지 판단할 것을 요구하고 있다.

 

즉 주어진 도시들이 연결되었는지를 판단하면 되므로 두가지의 풀이를 생각할 수 있는데

 

첫번째는 플로이드 워셜 알고리즘을 이용하여 쉽게 구하는 방법이고

 

두번째는 유니온 파인드를 이용해 각 정점들이 연결되어 있는지 판단하는 방법이다.

 

이 풀이에서는 유니온 파인드를 이용해보겠다.

    DisjointSet st(n);
    
    int loop; cin >> loop;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            int connex; cin >> connex;
            if (connex)
                st.merge(i, j);
        }

플로이드 워셜을 사용할게 아니므로 인접행렬을 구성하는 대신에 i 와 j 노드가 연결되어 있으면 바로 union 한다.

 

    int comp, target; cin >> target;
    bool flag(true);
    target = st.find(target - 1);
    for (int k = 0; k < loop - 1; ++k)
    {
        cin >> comp;
        if (target != st.find(comp - 1))
        {
            flag = false;
            break;
        }
    }
    
    cout << (flag ? "YES" : "NO");

target 변수에다가 첫번째 여행지를 대입해준다. 그 후 여행지 숫자 - 1번 만큼 루프를 돌면서

target과 comp가 서로 연결되어 있으면 (같은 집합에 소속되어 있으면) YES, 그렇지 않다면 NO를 출력하도록 하여

주어진 여행지들을 한코스로 여행할 수 있는지 판단하면 된다.

 

 

전체코드

#include <iostream>
#include <vector>

using namespace std;

struct DisjointSet
{
    vector<int> parent, rank;
    
    DisjointSet(int n) : parent(n), rank(n, 1)
    {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
    
    int find(int u)
    {
        if (parent[u] == u)
            return u;
        
        return parent[u] = find(parent[u]);
    }
    
    void merge(int u, int v)
    {
        u = find(u); v = find(v);
        
        if (u == v)
            return;

        if (rank[u] > rank[v])
        {
            int tmp(u);
            u = v; v = tmp;
        }
        
        parent[u] = v;
        
        if (rank[u] == rank[v])
            ++rank[v];
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n; cin >> n;
    
    DisjointSet st(n);
    
    int loop; cin >> loop;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            int connex; cin >> connex;
            if (connex)
                st.merge(i, j);
        }
    
    int comp, target; cin >> target;
    bool flag(true);
    target = st.find(target - 1);
    for (int k = 0; k < loop - 1; ++k)
    {
        cin >> comp;
        if (target != st.find(comp - 1))
        {
            flag = false;
            break;
        }
    }
    
    cout << (flag ? "YES" : "NO");
}