[백준/C++] 1976 여행 가자

1976번: 여행 가자

지난번에이어 이번에도 Union-Find 알고리즘을 이용해야하는 문제 입니다.

아직 Union-Find 알고리즘에 익숙하지않기때문에 참고 합니다.

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

// 백준 1976번 여행 가자 ( Union - Find 문제 )

int n, m; // 도시의수 n, 여행계획에 속한 도시들의수 m
int p[200]; // 도시의 수는 최대 200

int find(int x) { // 탐색
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

void union_node(int x, int y) { // 노드 합치기
	x = find(x);
	y = find(y);
	if (x < y) p[y] = x;
	else p[x] = y;
}

int main(void) {
	fastio;
	cin >> n >> m; // 도시의수 n, 여행계획에 속한 도시들의수 m

	for (int i = 1; i <= n; i++) p[i] = i;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int x;
			cin >> x;
			if (x == 1) {
				union_node(i, j);
			}
		}
	}
	int root;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		if (i == 0) root = find(x);
		else {
			if (find(root) != find(x)) { // 루트노드가 일치하지않으면 (경로 없음)
				cout << "NO";
				return 0;
			}
		}
	}
	cout << "YES"; // 루트노드가 일치하는경우에만 출력
	return 0;
}

2가지 풀이 방식을 참고할 수 있는 블로그 입니다.

백준 1976 C++ 여행 가자