Hanbit the Developer

[C] 백준 1976번: 여행 가자 본문

Algorithm/백준

[C] 백준 1976번: 여행 가자

hanbikan 2021. 6. 13. 17:24

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

 

1976번: 여행 가자

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

www.acmicpc.net

 

#include <stdio.h>
#include <stdlib.h>

int *parents;

int findParent(int x)
{
    if (parents[x] == x)
        return x;

    parents[x] = findParent(parents[x]);
    return parents[x];
}

void unionSets(int x, int y)
{
    int parentX = findParent(x);
    int parentY = findParent(y);

    if (parentX < parentY)
        parents[parentX] = parentY;
    else
        parents[parentY] = parentX;
}

int main()
{
    int i, j;

    int N;
    scanf("%d", &N);

    // parents 초기화
    parents = malloc(sizeof(int) * N);
    for (i = 0; i < N; i++)
        parents[i] = i;

    int M;
    scanf("%d", &M);

    int input;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            scanf("%d", &input);

            if (input == 1)
                unionSets(i, j);
        }
    }

    // 여행 계획 입력
    int isPossible = 0;
    scanf("%d", &input);
    int prevParent = findParent(input - 1);
    for (i = 1; i < M; i++)
    {
        scanf("%d", &input);

        if (findParent(input - 1) != prevParent)
        {
            isPossible = -1;
            break;
        }
    }

    // 출력
    if (isPossible == 0)
        printf("YES");
    else
        printf("NO");

    return 0;
}

 

유니온 파인드를 적용하면 매우 쉽게 풀 수 있는 문제이다. 연결되어있으면 하나의 집합으로 묶으면 되고, 마지막으로 일정을 확일할 때 해당하는 도시의 parents 값이 모두 일치하면 YES를 출력하고, 아니라면 NO를 출력하면 된다.