쾌락없는 책임 (공부)/알고리즘 문제풀이
[Algorithm] 백준 1976 여행가자 - C++, 분리집합
허스크
2022. 3. 9. 14:07
반응형
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
#include <iostream>
using namespace std;
int n, m;
int cityGroup[201];
int FindGroup(int x){
if(cityGroup[x] == x)
return x;
else return cityGroup[x] = FindGroup(cityGroup[x]);
}
void MergeGroup(int x, int y){
x = FindGroup(x);
y = FindGroup(y);
if(x == y) return;
cityGroup[x] = y;
}
int main(){
// init
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i = 0; i < 201; i++)
cityGroup[i] = i;
// input
cin >> n;
cin >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
int isConnect;
cin >> isConnect;
if(i == j) continue;
if(isConnect)
MergeGroup(i, j);
}
}
// search trip
int group, country;
cin >> country;
group = FindGroup(country);
for(int i = 1; i < m; i++){
int nextCountry;
cin >> nextCountry;
if(group != FindGroup(nextCountry)){
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
return 0;
}
일단 입력을 받으면서 연결이 되어 있다면 같은 그룹으로 묶은뒤 이후 m개의 입력을 받으면서 다른 그룹이 하나라도 있는지 살펴보면 되는 문제였습니다.
반응형