Life Engineering
[BOJ 1976] 여행 가자(C++) 본문
https://www.acmicpc.net/problem/1976
#include <bits/stdc++.h>
using namespace std;
int parents[201];
int find(int i){ //find parents
if (parents[i]==i){
return i;
}
else{
return parents[i]=find(parents[i]);
}
}
void union_(int a, int b){ //make a group
int pa=find(a);
int pb=find(b);
parents[pb]=pa;
}
int main(){
int N, M, c;
cin>>N>>M;
int plans[M];
bool isImpossible=false;
for (int i=1; i<=N; i++){
parents[i]=i;
}
for (int i=1; i<=N; i++){
for (int j=1; j<=N; j++){
cin>>c;
if (c==1){
union_(i,j); //연결되면 같은 그룹으로 합친다
}
}
}
for (int i=0; i<M; i++){
cin>>c;
plans[i]=c;
}
for (int i=0; i<M-1; i++){
if (find(plans[i])!=find(plans[i+1])){
isImpossible=true;
break;
}
}
if (isImpossible){
cout<<"NO"<<"\n";
}
else{
cout<<"YES"<<"\n";
}
return 0;
}
union-find 문제
연결되어있으면, union 시켜서 같은 그룹으로 만든다.
갈 수 있는지를 체크하는 것은 두 city가 서로 연결되었는지 체크하면 된다. 이때 같은 그룹(같은 부모를 가진 cities)인지 체크하는 Find 함수를 쓰면 된다.
'Problem Solving' 카테고리의 다른 글
[BOJ 2887] 행성 터널 (0) | 2021.08.12 |
---|---|
[BOJ 4195] 친구 네트워크 (C++) (0) | 2021.08.11 |
[BOJ 1261] 알고스팟 (C++) (0) | 2021.08.09 |
[BOJ 9202] Boggle (C++) (0) | 2021.07.22 |
[BOJ 1202] 보석 도둑(C++) (0) | 2021.07.22 |