1. 문제설명

여행 경로가 가능하면 1, 아니라면 0이라는 그래프가 주어진다.
어떤 여행 일정이 주어졌을 때 경로가 가능한지 판단하라
- 참고로 같은 점을 여러번 방문할 수 있다.
문제 분류
- Graph, Disjoint set

2. 알고리즘 설계

Union-Find 문제 였다.
각 노드의 연결 관계를 입력받으면서, 연결된 노드 중 하나를 다른 노드의 부모로 설정한다.
- 부모가 같다면 노드를 1회 혹은 여러번 방문해서 무조건 만날 수 있다는 뜻
로직
- 첫 계획을 미리 입력받는다.
- 다음 계획과 비교하여 부모가 같은지 체크한다.
  - 부모가 같다면, 반드시 만날 수 있다.
  - 다르다면, 만날 수 없음을 의미한다.
문제에 주어진 예제
- 처음 Union-Find 과정에서는 1번부터 순서대로 [2,3,3]이 부모가 된다.
  - index부터 우선적으로 실행되기 때문에 1번의 부모 2는 아직 갱신이 되지 않았다.
- 1번 부모와 2번 부모를 찾는다.
  - 1번의 부모는 2이고, 2번의 부모는 3이다.
  - 3의 부모는 자기 자신(3)이므로, 1번의 부모가 2번의 부모인 3이 된다.
- 2번 부모와 3번 부모를 찾는다.
  - 2번의 부모는 3번의 부모인 3, 3번은 3번의 부모인 3이 되어 값이 같다.
- 결국 1, 2, 3 모두 부모가 3번 노드이므로, 어떻게든 만날 수 있다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ=202;
int n, m, x, P[SZ];

int Find(int v) {
    if(v == P[v]) return v;
    else return P[v] = Find(P[v]);
}

void Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    P[u] = v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

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

    for(int u=1; u<=n; u++) {
        for(int v=1; v<=n; v++) {
            cin >> x;
            if(x != 0) Union(u, v);
        }
    }

    int past, here, chk=1;
    cin >> past;
    for(int i=1; i<m; i++) {
        cin >> here;
        if(Find(past) != Find(here)) {
            chk = 0;
            break;
        }
        past = here;
    }

    cout << (chk==1 ? "YES" : "NO");

    return 0;
}

BOJ 1976. 여행 가자

1. 문제설명

2. 알고리즘 설계

3. 전체 코드