[백준] 1976번: 여행 가자

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

1976번: 여행 가자

처음에 문제 초반만 보면 최소 스패닝 트리 등 탐색을 해야하나 싶지만 그렇지 않다.

각 도시의 연결성만 확인하면 되므로 유니온 파인드 알고리즘을 사용하였다.

 

이 때 parent 갱신을 주의하면 무난하게 풀 수 있는 문제이다.

 

#include <iostream>

using namespace std;
int city[201][201];
int parents[201];

int Find(int idx) {
    if(idx == parents[idx]) {
        return idx;
    }
    return parents[idx] = Find(parents[idx]);
}

void Union(int a, int b) {
    int parent_a = Find(a);
    int parent_b = Find(b);
    
    if(parent_a == parent_b) return;
    
    if(parent_a < parent_b) {
        parents[parent_b] = parent_a;
    }
    else {
        parents[parent_a] = parent_b;
    }
}
int main() {
    int N, M;
    
    cin >> N >> M;
    for(int i = 1;i <= N;i++) {
        parents[i] = i;
    }
    
    for(int i = 1;i <= N;i++) {
        for(int j = 1;j <= N;j++) {
            cin >> city[i][j];
        }
    }

    
    for(int i = 1;i <= N;i++){
        for(int j = 1;j < i;j++) {
            if(city[i][j]) {
                Union(i, j);
            }
        }
    }
    
    bool linked = true;
    int a, b;
    cin >> a;
    for(int i = 0;i < M - 1;i++) {
        cin >> b;

        if(Find(a) != Find(b)) {
            linked = false;
            break;
        }
        a = b;
    }
    
    if(linked) {
        cout << "YES" << '\n';
    }
    else {
        cout << "NO" << '\n';
    }
}