[코딩테스트 스터디/C++] 여행 계획

1.문제

임의의 두 여행지 사이에는 양방향 도로가 있다. 여행계획은 여행지의 수 N과 여행 계획에 속한 도시의 수 M으로 이뤄진다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하시오. (1 ≤ N, M ≤ 500)

2. 풀이 전 계획과 생각

• 서로소 집합 알고리즘 이용

3. 풀이

#include<iostream>
using namespace std;

int n, m;

int map[501][501];
int plan[501];

int parent[501];

// 특정 원소가 속한 집합을 찾기  
int find_parent(int x){
	if(parent[x]!=x) return find_parent(parent[x]);
	return x;
}

// 두 원소가 속한 집합을 합치기  
void union_parent(int a, int b){
	a = find_parent(a);
	b = find_parent(b);
	if(a<b) parent[b]=a;
	else parent[a]=b;
}

int main(){
	// 입력  
	cin>>n>>m;
	
	// 입력  
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>map[i][j];
	}	
	
	// 입력  
	for(int i=0;i<m;i++) cin>>plan[i];
	
	// 부모테이블에서 부모를 자기 자신으로 초기화  
	for(int i=1;i<=n;i++) parent[i]=i;
	
	// 입력 기반 union연산  
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i<j && map[i][j]==1) union_parent(i,j); 
		}
	}
	
	/*
	for(int i=1;i<=n;i++){
		cout<<find_parent(i)<<endl;
	}
	*/
	
	// 답 찾기  
	bool check=false;
	int check_parent = find_parent(plan[0]);
	for(int i=1;i<m;i++){
		if(check_parent!=find_parent(plan[i])) check=true;
	}
	
	// 답 출력  
	if(check==true) cout<<"NO";
	else cout<<"YES";
}

서로소 집합 알고리즘을 사용 후, 여행지로 입력한 곳이 모두 같은 집합에 속했는지 여부를 체크해, 만약 모두 같은 집합에 속해있으면 “YES”를, 아니면 “NO”를 출력함.

4. 풀이하면서 고민했던 점

• union연산을 할 때 양방향 그래프라 대각선으로 같은 의미가 있어 이것을 어떻게 처리할지 고민. 대각선을 기준으로 위쪽만 union연산을 함.

5. 문제를 풀고 알게된 개념 및 소감

• 서로소 집합 알고리즘에 대해 알게됨. 서로소 집합 자료구조 구현과 서로소 집합 알고리즘을 통한 문제해결 법을 알게되었다.