[백준 9466] 텀 프로젝트 (C++)

문제 링크: https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

1. 주의할 점

- 1 ->2, 2,3,4팀인 경우 생각해줘야 한다 (2->3, 3->4, 4->2를 통해 이미 2,3,4는 팀이 생성되었다고 가정)

- Deque를 이용한다

 

2. 구현

- A학생이 어떤 학생과 팀이 되고 싶어하는지를 Arr[A] 배열에 저장한다

- Check[] 배열을 전부 False로 초기화하여 팀 검사가 이루어지지 않았다고 설정한다

- 1~Num 까지의 학생들을 전부 조사하며 Check[] 값이 False인 경우 검사를 시작한다

- 1인 팀을 이루고 싶어한 학생의 경우, 바로 체크하여 다음 학생을 검사한다

- A 학생이 다른 학생과 팀을 하고 싶었다고 적은 경우, Deque에 삽입하고 While문을 시작한다

- Deque에 위치한 마지막 학생이 같이 하고 싶은 팀원을 Next에 저장한 후, Next가 아직 팀이 없다면 Next를 Deque의 마지막에 삽입하고 위의 과정을 반복한다

- 만약 Next가 팀이 있다면, Next가 Deque의 첫 번째 원소와 같은지 확인하고, 같다면 팀이 형성되었다고 한다

- 첫 번째 원소와 같지 않다면, 첫 번째 원소를 제거하고 Cnt++를 하여 팀을 이루지 못한 학생의 수를 계산한다

- 모든 학생들을 검사했다면, Cnt를 출력한다

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int arr[100001], num;
bool check[100001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> num;
		for (int i = 1; i <= num; i++) {
			cin >> arr[i];
			check[i] = false;
		}
		int cnt = 0;
		for (int i = 1; i <= num; i++) {
			if (!check[i]) {		//아직 검사 안한 경우
				if (arr[i] == i) {		//1인 팀을 이룰 경우
					check[i] = true;
					continue;
				}
				deque<int> dq;
				dq.push_back(i);
				check[i] = true;
				bool cycle = false;
				while (!dq.empty()) {
					int idx = dq[dq.size() - 1];
					int next = arr[idx];
					if (!check[next]) {
						check[next] = true;
						dq.push_back(next);
						continue;
					}
					while (!dq.empty()) {
						if (next == dq[0]) {		//cycle 생성
							cycle = true;
							break;
						}
						else {
							dq.pop_front();
							cnt++;
						}
					}
					if (cycle) break;
				}
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}