백준 9466번: 텀 프로젝트 (c++)

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

9466번: 텀 프로젝트

문제 해석

학생들은 프로젝트를 수행해야한다.

아래 조건이 있을 때 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

• 프로젝트 팀원 수에는 제한이 없다.
• 모든 학생은 프로젝트를 같이 수행하고 싶은 한 명의 학생을 선택해야 한다.
• 학생은 순서대로 1부터 n까지 번호로 표현한다. (2 <= n <= 100,000)
• 학생은 자기 자신을 선택할 수 있다.
• 1번 -> 2번 / 2번 -> 4번 / 4번 -> 1번 처럼 이루어져야 한 팀이 된다.

팀이 되는 경우를 예를 들어,

1  2  3  4  5  6  7 (학생의 번호)

3  1  3  7  3  4  6 (학생이 선택한 학생 번호)

이런 식으로 선택했다고 해보자. 이 경우에는 (3), (4, 7, 6)이 팀을 이룬다. 그러므로 1, 2, 5는 어느 팀에도 속하지 않는다. 따라서 답은 3이 된다.

---

풀이

학생들의 팀이 있는지 구하고 팀이 구해진 학생의 수를 모두 더해서 전체 학생 수에 빼는 식으로 코드를 작성하였다. 학생들이 오른손으로 팀을 하고 싶은 학생의 왼손을 잡는다고 했을 때 서로 손을 잡고 있는 상태가 팀을 이룬 상태라고 할 수 있다. 이런 것을 싸이클(cycle)이라고 한다. 다시 말 해 이 문제를는 싸이클(팀)을 구하고 그 싸이클의 크기(학생의 수)를 구하는 것이 중요하다고 할 수 있다.

 정점을 방문 했는지 나타내는 visited 배열 말고 정점 방문이 완전히 끝났는지 나타내는 finished 배열을 하나 더 추가 했다. visited[다음 정점] = true 이고, finished[다음 정점] = false이면 싸이클을 발견한 것이므로 그 싸이클의 크기를 구한다.

 아래 코드는 각 학생을 한 번씩 확인 하므로 O(n)의 시간복잡도를 가진다.

---

코드

#include <iostream>

using namespace std;

int T, n;
int tmp;
int ans = 0;
int v1[100001];
bool visited[100001];
bool finished[100001];

void dfs(int n) {
	visited[n] = true;

	if (visited[v1[n]] && !finished[v1[n]]) { // 싸이클이면
		for (int i = v1[n]; n != i; i = v1[i]) ans++; // 싸이클의 크기를 ans에 저장
		ans++; // 마지막 정점도 ++
	}
	if(!visited[v1[n]]) dfs(v1[n]);

	finished[n] = true;
}

int main() {
	cin >> T;
	for (int a = 0; a < T; a++) {
		fill(&visited[0], &visited[100001], false);
		fill(&finished[0], &finished[100001], false);
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> v1[i];
		}
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) dfs(i);
		}
		cout << n - ans << "\n"; // ans는 팀을 구한 학생 수 이므로 전체 - ans
		ans = 0;
	}

	return 0;
}

---

결과

 싸이클의 크기를 구하는 방법에 살짝 애를 먹었다. dfs, cycle을 연습할 수 있는 좋은 문제였다.

---

잘못된 정보가 있다면 알려주세요!