백준 BOJ 1976 - 여행 가자

유니온 파인드 == disjoint set 문제

소프트웨어 마에스트로 코테에 나왔다고 들어서 한번 다시 풀어보는 중이다.

 

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

1976번: 여행 가자

여행이 가능한지 안 가능한지만 묻고 있고, 여행 경로의 길이에 제한이 없기 때문에

특정 여행 경로로 두 도시가 이어질 수 있는지,

즉 모든 여행 계획에 속한 도시가

같은 도시집합 상에 포함되는지를 판별하면 되는 문제다.

 

여행 계획에 속한 도시들에 대해서 find() 를 진행하고,

그 결과로써 나온 집합의 어느 특정 도시를 셋에 넣어서 개수를 세줬다.

 

인접그래프가 인접행렬로 바뀐 단순구현 문제

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

int parent[234] = {0};
set<int> s;

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

void joint(int a, int b){
	a = find(a);
	b = find(b);
	parent[a] = b;
}

int main(){
	int N,M;
	int tmp;
	cin >> N >> M;
	
	for(int i=0; i<234; i++) parent[i] = i;
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			cin >> tmp;
			if(tmp){
				joint(i,j);
			}
		}
	}
	
	for(int i=0; i<M; i++){
		cin >> tmp;
		s.insert(find(tmp));
	}
	
	if(s.size() == 1) cout << "YES";
	else cout << "NO";
	return 0;
}