백준 9466 텀 프로젝트 [c++]
in Develop / Solving
c++
이거 문제 제목 팀 프로젝트인데 오타난건가 싶은 킹리적 갓심이 듬
문제 분석
- 각 학생들이 팀을 정해야 한다.
- 학생들은 누구와 팀을 하고 싶은지를 적어서 제출한다.
- 각 학생들이 원하는 학생들을 따라가다가 한 사이클을 이루게 되면, 그학생들은 팀이 된다.
- 예를 들어 아래 그림처럼 각 학생(윗줄)들이 원하는 학생(밑줄)을 적어 내면)
- 3은 솔로 팀을 이루게 되고, 4, 6, 7이 한 팀을 이루게 된다.
- 이 과정으로 팀을 짤 때, 팀에 속하지 못한 학생들의 수를 테스트케이스 별로 출력하여라.
입력조건
테스트 케이스 수 T
테스트 케이스 마다 {
학생 수 n
각 학생이 선택한 학생의 번호 배열
}
풀이과정
- ‘한 번 방문한 노드를 재방문하지 않는다.’
위 제약조건이 가능하도록 코드를 구성해야 한다.
그렇지 못하면 얄짤없이 시간초과(주로 80%에서)를 받게 된다.- 트리를 사용해서 푸는 사람도 있고, 풀이가 꽤 다양한 것 같다.
- 나는 서로소집합을 이용하여 풀었다.
- 각 학생들의 집합을 정해둔 뒤,
- 1번 학생부터 n번 학생 순으로 방문하며, 방문한 적이 있다면 패스하고, 없다면 팀을 만드는 함수를 호출한다.
- 팀을 만드는 함수는, 내가 선택한 학생과 나를 한 집합으로 묶고, 내가 선택한 학생으로 다시 팀을 만드는 함수를 호출한다.
- 이 과정에서 사이클이 생긴다면, 이는 팀이 생겼다는 의미이다. 그리고, 이 사이클의 시작과 끝은 사이클을 만들었을 때의 학생 번호와, 그 학생이 선택한 학생의 번호이다.
- 지금 상황은 팀을 만드는 함수를 여럿 재귀로 호출한 상황이고, 이 상태에서 사이클의 시작 부분까지 내려가며 한 팀으로 묶는다.
- 이 때 주의해야 할 점은, 1번 학생을 기준으로 재귀를 시작했다고 해서, 1번이 팀에 묶이지 않을 수도 있다는 점이다.
전체 코드
#include <iostream>
using namespace std;
int choose[100001];
int p[100001];
int solocount;
int parent(int x) {
if(p[x] == x) return x;
else return p[x] = parent(p[x]);
}
void join(int x, int y) {
p[parent(y)] = parent(x);
return;
}
int rot(int now) {
// union하고, cycle이 만들어졌는지 판단.
// 방문처리
int ch = choose[now];
choose[now] = 0;
// 방문한 적이 있으면 return
if(ch == 0) {
p[now] = now;
return -1;
}
if(parent(now) == parent(ch)) {
// cout << now << " " << parent(now) << " " << parent(ch) << endl;
solocount--;
if(now != ch) return ch;
else return -1;
}
join(now, ch);
int ret = rot(ch);
if(ret != -1) {
solocount--;
if(now == ret) return -1;
else return ret;
}
else {
// 부모 원래대로 돌려놓기.
p[now] = now;
return -1;
}
}
int main() {
int T;
cin >> T;
// 테스트케이스 반복
for(int t = 1; t <= T; t++) {
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> choose[i];
p[i] = i;
}
// 입력받기 끝.
solocount = n;
for(int i = 1; i <= n; i++) {
// 방문한 적이 없으면 함수 실행.
if(choose[i] != 0) rot(i);
}
cout << solocount << endl;
}
}
/*
테스트 케이스 모음
7
6
2 3 4 5 6 2
5
2 5 4 5 2
6
1 3 4 3 2 6
13
2 4 5 2 4 1 8 9 10 11 9 10 10
10
2 5 7 1 6 8 8 3 5 10
10
2 7 10 5 3 3 9 10 6 3
6
2 1 1 2 6 3
1
3
2
8
6
8
4
*/
