[백준] 여행 가자 (1976번)

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때(중복 가능) 가능한지 여부를 판별하는 프로그램을 작성하시오.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N * N 행렬을 통해 임의의 두 도시가 연결되었는지에 관한 정보가 주어진다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

---

간단한 disjoint-set 문제이다. 맵에서 1이면 두 도시가 연결되었다는 뜻이므로 union을 해주고 

여행 경로에서 루트가 다른 점이 하나라도 있으면 여행을 갈 수 없다는 뜻이므로 NO를 출력해준다. 

Union find만 구현하면 되는 쉬운 문제이다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%97%AC%ED%96%89%20%EA%B0%80%EC%9E%90(1976).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
using namespace std;
int p[201], parent[201];
int N, M;
int Find(int u) {
	if (parent[u] == u) return u;
	return parent[u] = Find(parent[u]);
}

void Union(int u, int v) {
	u = Find(u), v = Find(v);
	if (u == v) return;
	parent[u] = v;
	Find(u);
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i <= 200; i++) parent[i] = i;
	for (int tmp, i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> tmp;
			if (tmp == 1) Union(i, j);
		}
	}
	int past, here;
	bool canTrip = true;
	cin >> past;
	for (int i = 1; i < M; i++) {
		cin >> here;
		if (!canTrip) continue;
		if (Find(past) != Find(here)) canTrip = false;
		past = here;
	}
	if (canTrip) cout << "YES";
	else cout << "NO";
}