C++ / 백준 / 9466 / 텀 프로젝트

문제

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

문제풀이

queue와 DFS를 이용해서 풀었다.

테스트 케이스만큼 돌려야 하므로 T를 입력받고 T만큼 해당 작업을 반복한다.

 

1부터 N까지 숫자를 돌면서 탐색(DFS)을 한다.

다음 번호가 방문을 하지 않았다면, 방문 표시를 하고 큐에 다음 번호를 저장하고 탐색을 한다.

다음 번호가 방문한 번호라면, 순환하는 번호의 시작을 찾아야 하므로 q.front가 다음 번호일 때까지 pop을 한다.

다음 번호가 q.front와 같다면 남은 번호들은 서로 순환하는 팀이므로 team변수에 q.size()을 더한다.

그다음 탐색을 종료하고 방문하지 않은 숫자를 찾아 다시 탐색(DFS)을 한다.

 

팀을 짜기 위해 큐를 사용하므로 탐색(DFS)을 하기 전에는 탐색을 시작하는 번호 외에는 번호가 존재하면 안 되므로 미리 비워둔다.

팀에 속하지 않는 학생들의 수를 출력해야 하므로 학생수 - team을 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, team;

vector<int>num;
vector<bool>visit;
queue<int>q;

void DFS(int x) {
	int nxt(0);
	nxt = num[x];
	if (visit[nxt] == true) {
		while (!q.empty()) {
			if (nxt == q.front()) {
				team += q.size();
				return;
			}
			else {
				q.pop();
			}
		}
	}
	else if (visit[nxt] == false) {
		visit[nxt] = true;
		q.push(nxt);
		DFS(nxt);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T(0), idx(0), y(0), x(0);
	cin >> T;

	while (T--) {
		team = 0;
		cin >> N;
		num = vector<int>(N + 1, 0);
		visit = vector<bool>(N + 1, 0);

		for (idx = 1; idx <= N; ++idx) {
			cin >> num[idx];
		}

		for (idx = 1; idx <= N; ++idx) {
			if (visit[idx] == false) {
				q = queue<int>();
				q.push(idx);
				visit[idx] = true;
				DFS(idx);
			}
		}
		cout << N - team << '\n';
	}
}