[1976번] 여행 가자

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Disjoint-Set

2. Union Find :: http://www.crocus.co.kr/683

유니온 파인드에 대한 개념을 접목해 볼 수 있는 기본적인 문제이다.

0을 입력 받을 시 두번째, 세번째 값을 union하여 묶어주고

1을 입력 받을 시 두번째, 세번째 값을 find하여 루트가 같은지 비교하면 된다.

우선 입력을 받을 때 1->2면 2->1이기에 j가 i보다 큰 경우만(n*n의 행렬에서 대각선을 기준으로 오른쪽 영역의 값만)

merge를 해준다. 그리고 chk 변수를 두어 find를 계속 실행하여 한번이라도 루트가 같은 경우가 나타나지 않는다면

chk = false로 변경하고 break를 하여 탈출해준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
#define swap(a,b){int t = a; a = b; b = t;}
 
using namespace std;
 
// parent[a] = b :: a의 부모는 b다
int parent[201];
int level[201];
 
int find(int u)
{
    // 루트 노드이면 return u
    if (u == parent[u])
        return u;
 
    // 그 외에는 자신의 루트를 찾으러 간다.
    return parent[u] = find(parent[u]);
}
 
void merge(int u, int v)
{
    u = find(u);
    v = find(v);
 
    // 루트가 같다면 이미 같은 트리
    if (u == v)
        return;
 
    // u가 v보다 더 깊은 트리라면 swap
    if (level[u] > level[v])
        swap(u, v); // 항상 u가 더 작은 트리가 되도록 한다. 
 
    // u의 루트가 v가 되도록
    parent[u] = v;
 
    // u와 v의 깊이가 같을 때 v의 깊이를 늘려준다.
    if (level[u] == level[v]) 
        ++level[v];
}
 
int main()
{
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    // 초기에는 자신의 부모는 자기 자신
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        level[i] = 1;
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int val;
            scanf("%d", &val);
 
            if (j > i && val == 1)
                merge(i, j);
        }
    }
 
    bool chk = true;
    int val;
    scanf("%d", &val);
 
    int u = find(val);
    for (int i = 0; i < m - 1; i++)
    {
        scanf("%d", &val);
 
        if (u != find(val))
        {
            chk = false;
            break;
        }    
    }
 
    chk ? printf("YES") : printf("NO");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>