[백준/BOJ] 1976번: 여행 가자( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1976

 

풀이

이 문제는 도시 간의 여행 경로가 주어졌을 때, 도시 간에 도로가 있어서, 이 여행 경로를 따라 여행을 할 수 있는지 여부를 출력하는 문제입니다.

 

이 문제는 여러 가지 방법으로 해결할 수 있겠지만, 여기서는 Union-Find 알고리즘을 사용합니다.

이러한 Union-Find는 원소가 주어졌을 때, 이 원소가 어떤 집합에 속한 지를 판단하는 데 사용되는 알고리즘으로서, 먼저 이에 대한 내용을 알 필요가 있습니다.

[C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘

이 문제를 푸는 방법은 다음과 같습니다.

 

먼저, 입력으로 주어진 모든 도시들에 대하여,

한 도시   A   와 다른 도시   B   가 연결되어 있다면, 이 두 도시   A, B   를 같은 집합으로 묶습니다.

그렇게 되면, 이렇게 만들어진 집합 내의 모든 도시들 간에는 연결도로가 있다는 것을 알 수 있습니다.

 

이를 코드로 작성하면 다음과 같습니다.

#define SIZE 200
int parent[SIZE+1];

// Union-Find 알고리즘 ----------------------------
int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

void Union( int a, int b){
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;
}
//------------------------------------------------

int N, M;
cin >> N >> M;	// N은 도시 개수, M은 여행 경로 상의 도시 개수

for( int i = 0; i <= N; i++){   // 도시 집합 초기화
    parent[i] = i;  // root 
}

// 두 도시 간에 도로가 있으면 같은 집합으로 묶기
int bExistPath;
for( int i = 1; i <= N; i++){
    for( int j = 1; j <= N; j++){
        cin >> bExistPath;
        if ( bExistPath){
            Union( i, j);
        }
    }
}

위의 문제 설명에서 " i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다"라는 문장이 확 이해되지는 않는데, 이 얘기를 풀어쓰자면 다음과 같습니다.

// 문제 설명의 입력 예제에서 발췌
0 1 0	// 첫 번째 줄 ( i = 1 )
1 0 1	// 두 번째 줄 ( i = 2 )
0 1 0	// 세 번째 줄 ( i = 3 )

위에서 첫 번째 줄의 첫 번째 값인 0은, 1번 도시와 1번 도시 간에 연결도로가 없는 것을 나타냅니다. ( 자기 자신으로 가는 도로는 없다는 뜻 )

그리고, 첫 번째 줄의 두 번째 값인 1은, 1번 도시와 2번 도시 간에 연결도로가 있다는 것을 말합니다.

마찬가지로, 두 번째 줄의 첫 번째 값인 1은, 2번 도시와 1번 도시 간에 연결도로가 있다는 것을 말하는 것입니다.

 

이제,   M   개의 주어진 여행 경로에 있는 모든 도시가 같은 집합에 속해 있다면, 이 경로 상의 도시들은 도로로 연결되어 있고, 따라서, 이 여행 경로는 유효하다는 것을 알 수 있게 됩니다.

int city;
cin >> city;
int group = Find_Root(city);	// 첫 번째 도시가 속한 집합

bool bSuccess = true;
for( int i = 1; i < M; i++){
    
    cin >> city;
    
    // 다른 집합에 속한 도시가 있으면, 
    // 연결되지 않은 경로가 있다는 것을 말합니다.
    if ( Find_Root( city) != group){	
        bSuccess = false;
        break;
    }
}

if ( bSuccess){
    cout << "YES\n";
}
else{
    cout << "NO\n";
}

이를 판단하기 위해서 Find_Root 함수를 사용했습니다.

이러한 Find_Root는 도시가 속한 집합을 알려주는 함수입니다.

 

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE 200
int parent[SIZE+1];

int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

void Union( int a, int b){
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);   

    int N, M;
    cin >> N >> M;


    for( int i = 0; i <= N; i++){   // 도시 집합 초기화
        parent[i] = i;  // root 
    }
    
    int bExistPath;
    for( int i = 1; i <= N; i++){
        for( int j = 1; j <= N; j++){
            cin >> bExistPath;
            if ( bExistPath){
                Union( i, j);
            }
        }
    }

    int city;
    cin >> city;
    int group = Find_Root(city);
    
    bool bSuccess = true;
    for( int i = 1; i < M; i++){
        
        cin >> city;
        if ( Find_Root( city) != group){
            bSuccess = false;
            break;
        }
    }

    if ( bSuccess){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }

    return 0;
}