쾌락없는 책임 (공부)/알고리즘 문제풀이

[Algorithm] 백준 1976 여행가자 - C++, 분리집합

허스크 2022. 3. 9. 14:07
반응형
 

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

#include <iostream>
using namespace std;

int n, m;
int cityGroup[201];

int FindGroup(int x){
    if(cityGroup[x] == x)
        return x;
    else return cityGroup[x] = FindGroup(cityGroup[x]);
}

void MergeGroup(int x, int y){
    x = FindGroup(x);
    y = FindGroup(y);

    if(x == y)    return;

    cityGroup[x] = y;
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < 201; i++)
        cityGroup[i] = i;

    // input
    cin >> n;
    cin >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int isConnect;
            cin >> isConnect;

            if(i == j)  continue;

            if(isConnect)
                MergeGroup(i, j);
        }
    }

    // search trip
    int group, country;

    cin >> country;
    group = FindGroup(country);
    for(int i = 1; i < m; i++){
        int nextCountry;
        cin >> nextCountry; 

        if(group != FindGroup(nextCountry)){
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

 일단 입력을 받으면서 연결이 되어 있다면 같은 그룹으로 묶은뒤 이후 m개의 입력을 받으면서 다른 그룹이 하나라도 있는지 살펴보면 되는 문제였습니다.

반응형