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

🔗 문제

1976번: 여행 가자

1976번: 여행 가자

 

🖍 풀이

Union-Find로 간단히 풀 수 있는 문제였다.

 

여행가려는 지점(route)들이 같은 그래프에 속한다면 재방문을 하겠지만 아무튼 갈 수는 있다.

하지만 이어진 곳이 없는 아예 분리된 그래프라면 방문할 수 없다.

 

그래프 서로소 집합 구하기?.. 바로 유니온 파인드라는 생각이 들어 풀 수 있었다.

 

 

1. 연결된 지점을 받을 때마다 merge를 통해 한 그래프로 만들어준다. 

 

한 그래프로 만든다는 건  부모 노드가 같으면 같은 노드 (merge 함수 참고)

-  root[N]에 부모 노드를 저장해준다. 

 

2. 여행갈 경로들을 route에 저장한다. 

 

경로를 1,2 -> 2,3 -> 3,4... -> M-1,M 씩 짝지어서 같은 부모 노드를 가리키는지 확인한다. (isUnion 함수 참고)

만약 하나라도 같은 그래프에 속하지 않는다면 그 계획은 실패다. 

 

 

 

 

 

 

💾  소스

#include <iostream>

int root[25] = {0, };

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

void merge(const int a, const int b)
{
    int x = find(a);
    int y = find(b);
    
    if(x != y)
        root[y] = x;
}

bool isUnion(const int a, const int b)
{
    int x = find(a);
    int y = find(b);
    
    if(x == y)
        return true;
    else
        return false;
}

bool solve(const int M, const int* route)
{
    int from=0, to=1;
    
    while(to!=M)
    {
        if(!isUnion(route[from++], route[to++]))
            return false;
    }

    return true;
}

int main()
{
    int N, M;
    int route[10001] = {false, };
    
    std::cin >> N >> M;
    for(int i=1; i<=N; ++i)
        root[i] = i;
    
    bool inp = false;
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            std::cin >> inp;
            if(inp)
            {
                merge(i, j);
            }
        }
    }
    
    for(int i=0; i<M; ++i)
        std::cin >> route[i];
    
    std::cout << (solve(M, route) ? "YES" : "NO");
    
    return 0;
}