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

1976번: 여행 가자

cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> RootNode;
vector<int> Schedule;

int Find(int Node)
{
‌if (Node == RootNode[Node])
‌{
‌‌return Node;
‌}

‌return RootNode[Node] = Find(RootNode[Node]);
}

void Union(int NodeA, int NodeB)
{
‌int RootNodeA = Find(NodeA);
‌int RootNodeB = Find(NodeB);

‌int MinRootNode = min(RootNodeA, RootNodeB);
‌RootNode[RootNodeA] = MinRootNode;
‌RootNode[RootNodeB] = MinRootNode;
}

bool Determine(int NodeA, int NodeB)
{
‌return (Find(NodeA) == Find(NodeB));
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL);
‌cout.tie(NULL);

‌int N, M;
‌cin >> N >> M;

‌RootNode.reserve(N);
‌for (int i = 0; i < N; ++i)
‌{
‌‌RootNode.emplace_back(i);
‌}

‌for (int i = 0; i < N; ++i)
‌{
‌‌for (int j = 0; j < N; ++j)
‌‌{
‌‌‌int bLinked;
‌‌‌cin >> bLinked;

‌‌‌if (j < i + 1)
‌‌‌{
‌‌‌‌continue;
‌‌‌}

‌‌‌if (bLinked == 1)
‌‌‌{
‌‌‌‌Union(i, j);
‌‌‌}
‌‌}
‌}

‌Schedule.reserve(M);
‌for (int i = 0; i < M; ++i)
‌{
‌‌int City;
‌‌cin >> City;
‌‌Schedule.emplace_back(City - 1);
‌}

‌int Index = 0;
‌for (const int& City : Schedule)
‌{
‌‌if (Index == Schedule.size() - 1)
‌‌{
‌‌‌break;
‌‌}

‌‌int NextCity = Schedule[Index + 1];
‌‌if (!Determine(City, NextCity))
‌‌{
‌‌‌cout << "NO";
‌‌‌return 0;
‌‌}

‌‌++Index;
‌}

‌cout << "YES";
}

---

유니온 파인드 알고리즘을 사용해서 풀었습니다.

 

중복된 유니온 연산을 피하기 위해서 상삼각행렬 부분만 연산을 진행하도록 구현했습니다. (i == j도 제외)

그리고 입력 받은 여행 계획 순서를 배열에 저장한 다음

각 인접 노드끼리 서로 연결되어있는지 확인해서 답을 출력하도록 구현했습니다.