BOJ 1976 여행 가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

 

도시의 수가 주어지고 인접 행렬이 반사 행렬로 주어지니 무향 그래프로 봐도 된다.

이후 여행 갈 도시의 동선이 주어지는데 이를 path 배열로 받아줬다.

 

처음에는 DFS로 접근해서 

 

void DFS(int cur) {
	vis[cur] = true;
	for (int i = 1; i <= n; i++) {
		if (ar[i] && !vis[i]) {
			DFS(i);
		}
	}
}

 

이런 식으로 방문하지 않았다면 DFS를 돌리는 식으로 해줬는데 

 

in:
5
2
0 1 1 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 1 0
1 5

out:
NO

 

이런 식의 반례가 존재했다.

즉 모든 경우에 대해 DFS를 돌리기 때문에 vis배열에서도 모두 true로 나오게 되고 같은 컴포넌트인지 구분할 수 없었다.

이 부분은 따로 처리해주면 되겠지만 유니온 파인드를 배운 겸 유니온 파인드로 풀었다.

 

• n * n 만큼 입력을 받으면서 입력받은 값이 1 이면 i -> j를 union 해준다
• 이후 path 배열을 입력받고 path[0] 의 루트 노드를 찾는다
• path 배열을 돌면서 path[0] 의 루트 노드와 다르다면 갈 수 없는 동선이니 NO
• 아니라면 YES를 출력해준다

 

#include <iostream>
using namespace std;

int parent[1001], path[1001];

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

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) parent[y] = x;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, m, x;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) { 
		parent[i] = i;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> x;
			if (x) merge(i, j); 
		}
	}

	for (int i = 0; i < m; i++) cin >> path[i];

	int root = find(path[0]);

	for (int i = 0; i < m; i++) {
		if (root != find(path[i])) {
			cout << "NO" << endl; return 0;
		}
	}
	cout << "YES" << endl;

	return 0;
}