Life Engineering
[BOJ 9466] 텀 프로젝트 (C++) 본문
https://www.acmicpc.net/problem/9466
#include <bits/stdc++.h>
using namespace std;
int student[100001];
bool visited[100001];
bool group[100001];
int cnt;
void dfs(int x){
visited[x]=true;
int next=student[x];
if (!visited[next]){
dfs(next);
}
else if (!group[next]){ //방문 전에 했지만, 아직 결정되지 않은 애들(싸이클 발생!)
for (int i=next; i!=x; i=student[i]){
cnt++;
}
cnt++;
}
group[x]=true;
}
int main(){
int T;
vector<int> ans;
cin>>T;
while (T--){
cnt=0;
int n, x;
cin>>n;
for (int i=1; i<=n; i++){
cin>>x;
student[i]=x;
visited[i]=false;
group[i]=false;
}
for (int i=1; i<=n; i++){
if (!visited[i]){
dfs(i);
}
}
ans.push_back(n-cnt);
}
for (int i=0; i<ans.size(); i++){
cout<<ans[i]<<"\n";
}
return 0;
}
3시간 동안 고민하고.. 시간초과 및 틀렸습니다 여러번 받고.. 결국 답 보고 푼 문제.
DFS+싸이클 찾는 문제이다.
이 문제의 핵심은 싸이클의 갯수인데, 싸이클은 방문했던 정점들을 다시 지났고 그 정점이 아직 group 여부가 결정이 안된 상태일 때 생성된다. 그 지점부터 싸이클을 이루는 정점이 몇개 있는지 계산한다.
방문을 나타내는 visited 배열/ group이 만들어졌거나 아예 만들어지지 않는 경우가 결정된 경우를 나타내는 group 배열을 이용한다.
방문하지 않았으면 방문하고
전에 방문했는데 그룹여부가 결정이 안된 애들이면 싸이클이므로 싸이클에 해당하는 애들의 갯수를 세준다.
'Problem Solving' 카테고리의 다른 글
[BOJ 3830] 교수님은 기다리지 않는다 (C++) (0) | 2021.08.18 |
---|---|
[BOJ 2357] 최솟값과 최댓값 (C++) (0) | 2021.08.17 |
[BOJ 2887] 행성 터널 (0) | 2021.08.12 |
[BOJ 4195] 친구 네트워크 (C++) (0) | 2021.08.11 |
[BOJ 1976] 여행 가자(C++) (0) | 2021.08.10 |