백준 1976 여행가자

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

1976번: 여행 가자

 

여행가고싶다...

 

이 문제는 두 가지 방법으로 풀 수 있다.

첫번째는 BFS, 두번쨰는 Union-Find이다

 

두 코드 다 수록했다.

 

BFS로 푸는 건 각 정점간의 연결관계를 확인하는 방법이다. 

 

예를 들어서 A - B, B - C가 연결되어 있을 때 A를 시작점으로 BFS를 돌리면 당연히 C까지 연결된다. 

A를 시작으로 하는 BFS를 돌리면서 도착하는 정점마다 A와 연결되어있다고 표시해두면 문제를 풀 수 있다. 

 

/* 여행 가자 */

#include <iostream>
#include <queue>

using namespace std;

int n_of_city, n_of_travel;
bool edge[200 + 1][200 + 1];
int travel[1000 + 1];

void input();
void solve();

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> n_of_city >> n_of_travel;
	for (int i = 1; i <= n_of_city; i++) {
		for (int j = 1; j <= n_of_city; j++) {
			cin >> edge[i][j];
		}
	}

	for (int i = 1; i <= n_of_city; i++) {
		edge[i][i] = true;
	}

	for (int i = 1; i <= n_of_travel; i++) {
		cin >> travel[i];
	}
}

void bfs(int idx) {
	queue<int> q;
	q.push(idx);
	bool is_visit[200 + 1] = { false, };
	is_visit[idx] = true;
	while (!q.empty()) {
		int curr = q.front();
		q.pop();

		for (int i = 1; i <= n_of_city; i++) {
			if (edge[curr][i] == true && is_visit[i] == false) {
				edge[idx][i] = true;
				edge[i][idx] = true;

				is_visit[i] = true;

				q.push(i);
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= n_of_city; i++) {
		bfs(i);
	}

/*	for (int i = 1; i <= n_of_city; i++) {
		for (int j = 1; j <= n_of_city; j++) {
			cout << edge[i][j] << ' ';
		}cout << endl;
	}*/

	for (int i = 1; i <= n_of_travel-1; i++) {
		if (edge[travel[i]][travel[i + 1]] == false) {
			cout << "NO" << '\n';
			return;
		}
	}

	cout << "YES\n";
	return;
}

 

두 번째는 Union-Find, (Disjoint Set) 방법이다.

 

도시 간 관계를 입력받을 때 둘의 부모 자식관계를 형성하고 

여행 경로를 받을 때 입력된 숫자들이 같은 부모를 가졌는지 체크한다.

 

부모가 다르다면, 둘은 연결될 수 없으므로 False이다!

 

/* 여행 가자 */

#include <iostream>
#include <queue>

using namespace std;

int n_of_city, n_of_travel;
bool edge[200 + 1][200 + 1];
int travel[1000 + 1];
int parent[200 + 1];

void input();

int find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]);
}

void unions(int x, int y) {
	int px = find(x);
	int py = find(y);
	parent[px] = py;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();

	return 0;
}

void input() {
	cin >> n_of_city >> n_of_travel;

	for (int i = 1; i <= n_of_city; i++) {
		parent[i] = i;

		for (int j = 1; j <= n_of_city; j++) {
			cin >> edge[i][j];
			if (edge[i][j] == true) { // 연결한다. 
				unions(i, j);
			}
		}
	}

	cin >> travel[1];
	for (int i = 2; i <= n_of_travel; i++) {
		cin >> travel[i];
		if (parent[travel[i - 1]] != parent[travel[i]]) {
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
	return;
}