백준 1976번 _ 여행 가자

2020-04-25 · 배운 것 · 3분 읽기

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

1976번: 여행 가자

풀이방법

그냥 유니온 파인드 알고리즘 이용하면 답 나옴(밑의 url참조)
https://blog.fxjodo.com/blog/22/

백준 1197번 _최소 스패닝 트리

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int parents[201];
int N, M;

void makeParents()
{
	for (int i = 1; i <= N; i++)
		parents[i] = i;
}

int getParent(int a)
{
	if (parents[a] == a) return a;
	return parents[a] = getParent(parents[a]);
}

void Union(int a, int b)
{
	a = getParent(a);
	b = getParent(b);
	if (a == b)
		return;
	parents[b] = a;
}

void Input()
{
	cin >> N;
	cin >> M;
	makeParents();
	int value;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> value;
			if (value == 0)
				continue;

			Union(i, j);
		}
	}
}

void solve()
{
	vector<int>travel;
	int tmp;
	for (int i = 0; i < M; i++)
	{
		cin >> tmp;
		travel.push_back(tmp);
	}

	bool possible = true;
	for (int i = 0; i < M - 1; i++)
	{
		if (getParent(travel[i]) != getParent(travel[i + 1]))
			possible = false;
	}
	if (possible)
		cout << "YES";
	else
		cout << "NO";
}

int main()
{
	Input();
	solve();
	return 0;
}

후기

ㅎㅎ