백준 9466번: 텀 프로젝트
텀 프로젝트
아이디어
그냥 dfs하면 안되고 ”학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.” 조건을 잘 걸러내야 한다. 즉 그래프에서 한바퀴 도는 경우가 생겼을 그 사람들끼리는 팀이라고 기록해줘야 한다.
코드
#include <bits/stdc++.h>
using namespace std;
// 0: not visited
// 1: checking
// 2: in team
// 3: no team
int solve(vector<int> &v) {
int visited[v.size()] = {};
vector<int> select;
for (int i = 1; i < v.size(); i++) {
if (visited[i] > 0) continue;
select.push_back(i);
int next = i;
while (visited[next] == 0) {
visited[next] = 1;
next = v[next];
select.push_back(next);
}
select.pop_back();
if (visited[next] == 1) { // team
auto iter = select.begin();
while (*iter != next) {
visited[*iter] = 3;
iter++;
}
while (iter != select.end()) {
visited[*iter] = 2;
iter++;
}
}
else { // no team
for (int x : select) {
visited[x] = 3;
}
}
select.clear();
}
int cnt = 0;
for (int x : visited) {
if (x == 3) {
cnt++;
}
}
return cnt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> v;
v.push_back(0);
while (n--) {
int x;
cin >> x;
v.push_back(x);
}
cout << solve(v) << '\n';
}
return 0;
}
설명
visited 배열에 숫자 1을 기록하면서 탐색한다. 현재 탐색중인 학생들을 select 벡터에 집어넣는다. 그러다 다음으로 탐색할 학생의 visited자리가 1이면 한바퀴 돌아서 팀이 생긴 것이다. 이 때 한바퀴 도는데 포함되지 않은 학생들은 앞으로 영원히 팀이 없을 예정이기 때문에 visited배열에 3을 기록하고 한바퀴 도는데 포함된 학생들은 2를 기록한다.
여담
이거 그냥 그래프 사이클 찾기 문제인데 좀 복잡하게 푼듯
Author And Source
이 문제에 관하여(백준 9466번: 텀 프로젝트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-9466번-텀-프로젝트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)