Hanbit the Developer
[C] 백준 1976번: 여행 가자 본문
https://www.acmicpc.net/problem/1976
#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를 출력하면 된다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 2785번: 체인 (0) | 2021.06.16 |
---|---|
[C] 백준 1717번: 집합의 표현 (0) | 2021.06.13 |
[Python] 10165번: 버스 노선(플레 처음으로 성공한 날) (0) | 2021.06.11 |
[Python] 백준 2036번: 수열의 점수(시간복잡도 1등) (0) | 2021.06.10 |
[Python] 백준 12018번: Yonsei TOTO (0) | 2021.06.08 |