문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

문제 링크

풀이

union-find 알고리즘으로 간단하게 해결이 가능하다.
두 도시가 이어져 있다면 같은 집합으로 묶어둔다.

입력의 마지막 행으로 여행할 도시가 주어지는데 이때의 도시 리스트들이 전부 같은 집합에 들어있는지 확인하여 그 값을 출력하면 된다.
첫 도시를 find()함수로 root 도시를 구하고 그 도시를 기준으로 여행할 도시 리스트의 남은 도시들도 find()호출을 해 같은 집합에 속해있는지 확인한다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, m;
int* depth;
int* root;

int findSet(int x){
    if (root[x] == x){
        return x;
    }
    else {
        return root[x] = findSet(root[x]);
    }
}

void unionSet(int x, int y){
    x = findSet(x);
    y = findSet(y);

    if (x == y) return;

    if (depth[x] > depth[y]){
        root[y] = x;
    }
    else if(depth[x] < depth[y]){
        root[x] = y;
    }
    else{
        root[x] = y;
        depth[y]++;
    }
}

int main(){
    cin.tie(0);
	cin.sync_with_stdio(false);
	ios_base::sync_with_stdio(false);

    cin >> n;
    cin >> m;
    depth = (int*)malloc(sizeof(int) * n);
    root = (int*)malloc(sizeof(int) * n);
    vector<int> plan(m);

    for(int i=0; i < n; i++){
        root[i] = i;
        depth[i] = 0;
    }

    for(int i=0; i < n; i++){
        for(int j=0; j < n; j++){
            int temp;
            cin >> temp;

            if (temp == 1){
                unionSet(i, j);
            }
        }
    }
    
    for(int i=0; i < m; i++){
        int temp;
        cin >> temp;
        plan[i] = temp-1;
    }


    int target = findSet(plan[0]);
    string answer = "YES";
    for (int i=1; i < m; i++){
        if (target != findSet(plan[i])){
            answer = "NO";
            break;
        }
    }

    cout << answer << endl;
    return 0;
}