백준 1976번 여행 가자

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

Union Find(=Disjoint Set) 자료구조를 사용하는 쉬운 난이도의 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 초기에는 모든 도시의 부모가 자기 자신입니다.

2. 인접한 도시끼리 집합을 합쳐줍니다.(merge 함수를 통해)

3. 마지막에 M개의 도시들이 모두 같은 집합 내에 속해 있는지 확인합니다.

i) 모두 같은 집합이면 여행을 갈 수 있습니다.

ii) 하나라도 다른 집합에 있다면 여행을 갈 수 없습니다.

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 200 + 1;

 

int N, M;

int arr[MAX];

 

//부모 찾는 연산

int findParent(int num)

{

        if (arr[num] < 0)

                 return num;

 

        int parent = findParent(arr[num]);

        arr[num] = parent;

        return parent;

}

 

void merge(int aParent, int bParent)

{

        //집합의 크기가 더 큰 쪽으로 합쳐진다

        if (abs(aParent) >= abs(bParent))

        {

                 arr[aParent] += arr[bParent];

                 arr[bParent] = aParent;

        }

        else

        {

                 arr[bParent] += arr[aParent];

                 arr[aParent] = bParent;

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        //초기에는 모든 원소의 부모가 자기 자신

        memset(arr, -1, sizeof(arr));

       

        //인접한 도시들끼리 한 집합으로 합쳐준다

        for (int i = 1; i <= N; i++)

                 for (int j = 1; j <= N; j++)

                 {

                         int connected;

                         cin >> connected;

 

                         if (connected)

                         {

                                 int aParent = findParent(i);

                                 int bParent = findParent(j);

                                 if (aParent == bParent)

                                          continue;

 

                                 merge(aParent, bParent);

                         }

                 }

       

        int root;

        bool possible = true;

        //주어진 도시들이 모두 같은 집합에 있는지 확인

        for (int i = 0; i < M; i++)

        {

                 int city;

                 cin >> city;

 

                 //첫 번째 도시의 루트를 찾아준다

                 if (i == 0)

                         root = findParent(city);

                 else

                 {

                         if (root != findParent(city))

                         {

                                 possible = false;

                                 break;

                         }

                 }

        }

       

        if (possible)

                 cout << "YES\n";

        else

                 cout << "NO\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~