백준 / 1976 / 여행 가자 / C++ / Union Find 알고리즘

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

1976번: 여행 가자

이번 문제의 핵심은 '연결되어있기만 하다면' 다른 곳을 통하여 목적지까지 갈수 만 있으면 되는 것 입니다.

그래프의 연결관계를 확인하고 싶을 때, 사용되는 Union Find알고리즘으로 문제를 풀어보았습니다. 

입력으로 주어지는 정보를 바탕으로 두 도시가 연결되어있다면 Union함수를 통해 이어주고, 마지막으로

답을 구하기 위한 최종 여행 루트의 연결관계를 파악해서 그 중 하나의 도시라도 이어져있지 않은 도시가

존재한다면 No를 출력하고 모두가 연결되어 있다면 어떻게든 다 순회할 수 있기 때문에 Yes를 출력합니다.

 

처음에 myParent행렬에서 부모노드를 자기 자신으로 초기화하여 설정하고, 입력으로 주어지는 정보에서

1 , 즉 연결되었음을 알려줄 때 Union함수를 통해 두 도시를 같은 집합으로 묶어줍니다. 예제 입력에서

(1,2)의 값이 1로 주어졌는데 , 둘의 부모노드의 값이 다르기 때문에 Union을 통해 연결해주고 (2,1)에서는

이미 연결되어 있음을 알기 때문에 Union함수에서 return을 만나 연결해줄 필요없이 함수가 종료하게 됩니다.

그 후에 마지막 줄인 여행의 최종 루트를 destList라는 배열에 넣고, 첫번째 원소의 값을 Find함수를 통해 

부모노드의 값을 받아오고 다음 원소들 부터 차례대로 Find함수를 통해 부모노드를 찾아 하나라도 다른 값이

존재한다면 서로 다른 집합 , 즉 이어져 있지 않다는 것을 의미하기 때문에 No를 출력하고 모두 다 같은 부모노드를

갖는다면 , 즉 같은 집합에 속해있다면 모든 목적지 방문이 가능하기 때문에 Yes를 출력합니다. 

 

★틀린 내용이 있을수 있습니다 ! 댓글로 언제든 수정해주시면 감사하겠습니다. 또한 , 질문 주시는 부분은 제가 아는 선에서 성심성의껏 답변드리겠습니다.

#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
int destList[1000];
int adjArr[201][201];
int myParent[201];
 
int findNode(int x)
{
    if (myParent[x] != x)
    {
        return findNode(myParent[x]);
    }
    else
        return myParent[x];
}
 
void uinonNode(int x, int y)
{
    x = findNode(x);
    y = findNode(y);
 
    if (x == y)
        return;
 
    if (x < y)
        myParent[y] = x;
    else
        myParent[x] = y;
        
}
 
int main()
{
    cin >> N >> M;
    
    for (int i = 1; i <= N; i++)
    {
        myParent[i] = i;
    }
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> adjArr[i][j];
            if (adjArr[i][j] == 1)
                uinonNode(i, j);
        }
    }
 
    for (int i = 0; i < M; i++)
    {
        cin >> destList[i];
        
    }
 
    int oneValue = findNode(destList[0]);
 
    for (int i = 1; i < M; i++)
    {
        if (oneValue != findNode(destList[i]))
        {
            cout << "NO" << endl;
            return 0;
        }
        
    }
 
    cout << "YES" << endl;
    return 0;
    
}