1976 여행 가자

1976 여행 가자 (c++)

문제

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

접근 방식

Union Find

1. 각 노드의 엣지 여부가 N*N 행렬로 입력된다.
   1. 0이면 연결되지않은 것
   2. 1이면 i, j를 Union
2. 여행지 M 개가 차례로 입력된다.
   1. now, next로 받아서 Find(now) == Find(next) 로 계속되면 “YES”
   2. 중간에 하나라도 같은 root가 아니라면 “NO”

문제 풀이

#include <iostream>
using namespace std;

int Find(int x, int* p)
{
    if (p[x] == x) return x;

    return p[x] = Find(p[x], p);
}

void Union(int a, int b, int* p)
{
    a = Find(a, p);
    b = Find(b, p);
    if (a == b) return;
    else if (a < b) p[b] = a;
    else p[a] = b;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M, num, now, next, p[201];
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) p[i] = i;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> num;
            if (num) Union(i + 1, j + 1, p);
        }
    }
    for (int i = 0; i < M; ++i)
    {
        if (!i) cin >> now;
        else
        {
            cin >> next;
            if (Find(now, p) != Find(next, p))
            {
                cout << "NO" << endl;
                return 0;
            }
            now = next;
        }
    }
    cout << "YES" << endl;
    return 0;
}

다시 생각해볼 점

1. 결국 A->B로 갈 수 있냐는 건 A와 B의 root 가 같냐고 물어보는 질문이다.
2. 서로 연결되어있는지를 물어보는 문제에서 Union Find 알고리즘을 써보는 것이 좋겠다.