[C++] 백준 1976 여행 가자

#include <iostream>
#include <vector>
 
using namespace std;
 
// union-Find 여행 하려는 곳의 부모가 모두 같다면 성공                                             
 
int n,m;
vector<int> travle;
int arr[201];
 
void init() {
    for(int i=0; i<201; i++) {
        arr[i] = i;
    }
}
 
int find(int x) {
    if(arr[x] == x) { return x; }
    return arr[x] = find(arr[x]);
}
 
bool isUnion(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) { return true; }
    return false;
}
 
void merge(int x,int y) {
    x = find(x);
    y = find(y);
    if(x == y) { return; }
    
    arr[y] = x;
}
 
void input() {
    cin >> n;
    cin >> m;
    int tmp;
    init();
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {        
            cin >> tmp;
            if(tmp == 1) {
                merge(i,j);
            }
        }
    }
    
    for(int i=0; i<m; i++) {
        cin >> tmp;
        travle.push_back(tmp);
    }
}
 
void solve() {
    for(int i=1; i<travle.size(); i++) {
        if(!isUnion(travle[i-1],travle[i])) {
            cout << "NO";
            return;
        }
    }
    
    cout << "YES";
    return;
}
 
int main() {
    input();
    solve();
    
}

 

 

union-find 만 사용할 줄 안다면 쉽게 풀리는 문제 

 

중요한건 이런 문제를 마주쳤을 때 union-find 알고리즘을 사용한다는 발상을 해 내는 것이다.

 

 

** 동혁이가 계획대로 여행을 가려면 한점 잇기를 했을때 끊기는 부분이 없어야 한다. **

 

끊기는 부분이 없다 == 부모 노드가 같다

 

라는 발상을 통해 union-find 로 접근해야 한다.