[BFS]-응용-텀 프로젝트

< BFS > - < 골드 3 >

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

9466번: 텀 프로젝트

---

[ 9466 ] 텀 프로젝트

 

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

 

:: 입력 ::

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

:: 출력 ::

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

---

 

구현 방식이 감조차 오지 않아서 조금 고민하다가 바로 답안 코드를 보고 따라 쳐보면서 로직을 이해했다 종이에 손수 그려가면서 이해했는데 정형화 된 bfs를 사용하는 문제는 이제 어느정도 풀 수 있지만 이정도의 응용은 아직 힘든 듯 포인터를 옮기듯 반복문 안에서  cur = arr[cur] 해주는 부분을 떠올리지 못했다 +  state[cur] = x 해서 해당 학생이 루프를 도는 중이라는 것을 표시해주는 아이디어도 떠올리지 못함 ㅠ  블로그 풀이 https://blog.encrypted.gg/499 사이클 내부의 요소인지 아닌지를 판단하려면 (시간복잡도 고려없이) 시작점에서 계속 화살표를 따라가면 됨 그러다보면 이미 방문된 곳을 방문하게 될텐데 시작점이 싸이클 내부의 요소라면  처음 만나는 중복된 곳이 자기 자신이겠지만 시작점이 싸이클 내부의 요소가 아니라면 처음 만나는 중복된 곳은 싸이클 내부의 한 요소가 될 것 이 방법은 모든 요소가 요소의 수만큼 이동을 해야하기 때문에  시간복잡도 O(n^2) 의 방법 이를 O(n)으로 줄이기 위해서는 이전에 방문했던 칸을 이용하는 아이디어가 필요함 싸이클에 포함된 요소에 표시를 해두면 시간 복잡도를 줄일 수 있음 아래의 이미지 참고 + 특히 BFS를 여러 시작점에 대해서 진행해야 할 때 visited 배열을 매번 새로 만들거나 초기화를 시키면 O(N^2)이 되지만 visited 여부를 체크하는 값을 매번 다른 값을 넣어 O(N)으로 만드는 테크닉은 알아두시면 언젠가 좀 어려운 문제를 풀 때 쓰일수도 있으니 좋을 것 같습니다.

 

  정답  코드  

-#include <iostream>

#include <algorithm>

#include <vector>
#include <string>

using namespace std;

int arr[100005];
int n;
int state[100005];

const int NOT_VISITED = 0;
const int CYCLE_IN = -1;

void run(int x) {
	// 아직 방문되지 않은 학생의 번호가 들어옴
	int cur = x;

	while (true) {
		// state[cur] 에 해당 학생의 루프가 도는 중이라고 표시해줌
		state[cur] = x;
        	// 해당 학생이 지목중인 학생의 번호를 cur에 저장
		cur = arr[cur];

		// 이번 방문에서 지나간 학생에 도달했을 경우
		if (state[cur] == x) {
			while (state[cur] != CYCLE_IN) {
				state[cur] = CYCLE_IN;
				cur = arr[cur];
			}
			return;
		}
		// 이전 방문에서 지나간 학생에 도달했을 경우
		else if (state[cur] != 0) return;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	// 테스트 케이스의 갯수를 입력 받음
	int t;
	cin >> t;

	while (t--) {
		// 학생 수를 입력 받음
		cin >> n;
		// 학생 수 만큼 state 배열을 0으로 초기화해줌 (arr[1] ~ arr[n])
		fill(state + 1, state + n + 1, 0);
		// 학생이 누구를 골랐는지 arr에 저장
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		int ans = 0;

		// 방문되지 않았다면 해당 칸에 대해 bfs를 돌림
		for (int i = 1; i <= n; i++) {
			if (state[i] == NOT_VISITED) run(i);
		}

		int cnt = 0;

		for (int i = 1; i <= n; i++) {
			if (state[i] != CYCLE_IN) cnt++;
		}

		cout << cnt << "\n";
	}
}