BOJ 9466 텀 프로젝트

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

1. 문제요약

- 학생들이 팀을 이룸

- 1 2 3 4 5 6 7

  3 1 3 7 3 4 6

- 2 -> 1 -> 3(3) <- 5

  4 -> 7 -> 6 -> 4

- 3은 혼자서 팀을 이루고 4, 7, 6은 세명이서 팀을 이룸

- 팀에 속하지 않은 학생은 1, 2, 5 로 3명

- 팀에 속하지 않은 학생수는?

2. 접근방법

- 방법1. 위상정렬

  한 정점에서 나가는 간선은 무조건 1개

  한 정점에 들어오는 간선은 여러개

  

  들어오는 간선의 수를 헤아린 뒤에 한 정점을 방문시 다음 정점으로 들어가는 간선을 하나씩 없앰

  사이클을 형성할려면 무조건 들어오는 간선이 하나는 존재 하므로

  모든 정점을 방문하면서 들어가는 간선이 없는 정점을 방문하면 팀이 없는 사람만 골라 낼 수 있음

사이클을 형성하지 않는 노드만 방문하여 갯수를 헤아림

노드를 방문하는 조건은 해당 노드로 들어오는 간선이 없으면 사이클을 형성하지 않는다는 의미이므로 간선이 없을 때 방문

for문으로 노드 1부터 노드 n까지 방문

아.. 음 그림이 좀 잘못됬는데 노드 5에서 노드 3으로 들어가는 화살표 방향이 되어야함.

<fig 1>

초기 해당 노드로 들어오는 간선의 수 초기화

노드 1은 들어오는 간선의 수가 1 이므로 방문하지 않음

<fig 2>

노드 2는 들어오는 간선의 수가 없으므로 첫번째로 방문하게 됨

<fig 3>

노드 2를 방문하면서 노드 1로 이어지는 간선을 없애면 노드 1은 방문 가능한 상태가 되어 방문 하게 됨

노드 1을 방문하면서 노드 3으로 들어가는 간선의 수를 하나 없애도 노드 3은 들어오는 간선의 수가 2이므로 방문하지 않음

<fig 4>

노드 4, 노드 7, 노드 6은 들어오는 간선의 수가 1이므로 방문하지 않음

<fig 5>

노드 5는 들어오는 간선의 수가 0이므로 방문

노드 5를 방문하면서 노드 3으로 들어가는 간선의 수를 하나 없애도 노드 3은 간선의 수가 1 이므로 방문하지 않음

실제로 코드는 노드 4를 확인한 다음 노드 5를 확인함(for문 이므로)

- 방법2. stack

  현재까지 방문한 정점을 stack에 쌓은다음 방문했던 정점을 방문했을 때 스택의 어는 부분에 있는지 확인하여 사이클이 아닌 노드의 갯수를 합침

  check[n]은 방문을 나타내며 0은 방문 하지 않음

                                      1은 방문했지만 아직 팀은 아님

                                      2는 팀에 속함

  check[n]이 1인경우 사이클을 이루는 경우와 이루지 않는 경우로 나눌 수 있는데

  stack을 돌려보고 해당 정점이 스택에 없으면 사이클이 없는 것이므로 현재까지 방문했던 노드갯수를 합침

<fig 5>

노드 1을 방문하고 stack에는 1, check[1] = 1

<fig 6>

노드 3을 방문하고 stack에는 3, check[3] = 1

<fig 7>

노드 3은 다시 노드 3을 방문 즉, check[3] = 1 stack을 돌면서 노드 3이 있는지 확인 후 check[3] = 2

<fig 8>

노드 2를 방문 stack에는 2, check[2] = 1

노드 1이 check[1] = 1인 상태이지만 스택에 없기 때문에 현재까지 방문했던 노드 2를 팀을 이루지 않는 인원에 합산

<fig 9>

노드 4, 7, 6을 순서대로 방문 stack 4, 7, 8, check[4] = check[7] = check[6] = 1

<fig 10>

노드 6의 다음 노드는 노드 4 노드 4는 check[4] = 1이므로 노드 4가 스택에 있는지 확인 후 해당 노드 4 부터 노트 6까지 check[n] = 2로 변경

stack에 8이 아니라 6

<fig 11>

노드 5를 방문 stack 5, check[5] = 1

노드 5의 다음 노드는 노드 3 노드 3은 check[3] = 2이므로 현재까지 방문했던 노드 5를 팀에 속하지 않는 인원에 합산

- 방법3. 1 : 1대응 그래프 특성

  방문하는 노드에 방문 순서를 매김

  한 컴포넌트에서 처음 방문한 노드의 숫자가 한번 방문했던 노드를 다시 방문한 노드의 숫자 보다 작거나 같으면 사이클을 형성하고 있음

  팀을 이루고 있는 전체 인원을 합산하여 전체 학생 수에서 팀 인원을 제외

  check[n]을 노드 n의 방문 순서,

  student[n]을 친구간 연결이라 한다면

  

  if(check[student[now] >= check[start]) team += cnt - check[student[now]] + 1

  ans = n - team

<fig 12>

최초에 모든 노드는 방문한 적이 없으므로 check[n] = 0

cnt = 1

노드 1을 최초 방문 이므로 check[1] = 1

<fig 13>

cnt = 2

노드 3은 노드 1 다음 방문이므로 2번째 check[2] = 2

check[노드 3] = 2

check[1] = 1 이므로

team += 2 - 2 + 1 = 1

<fig 14>

cnt = 3

check[노드 2] = 3

check[노드 1] = 1 이므로 앞므로 방문할 노드 1의 check[노드 1]의 값이 더 작음

<fig 15>

cnt = 4

check[노드 4] = 4

check[노드 7] = 5

check[노드 6] = 6

노드 6은 노드 4를 재 방문

check[노드 6] = 6

check[컴포넌트 시작점 즉, 노드 4] = 4

team = 6 - 4 + 1 = 3

<fig 16>

cnt = 7

check[노드 5] = 7

노드 5는 노드 3을 재방문

check[노드 5] = 7

check[노드 3] = 2

3. 시간복잡도

- 방법 1. O(n)

- 방법 2. O(2n)

- 방법 3. O(n)

4. 회고

- 음 첫번째꺼는 인터넷에서 줍줍

- 두번째는 스스로 고민

- 세번째는 맞춘 후에 맞은사람 꺼 봄

- 세번째 방법같은 생각은 어떻게 하지...

소스코드 : 방법 1

#include<iostream>
using namespace std;

int t;

int main(void){
	cin >> t;
	while (t--){
		int n, student[100001], finish[100001], ans = 0;
		bool check[100001];

		cin >> n;
		for (int i = 1; i <= n; i++){
			check[i] = false;
			finish[i] = 0;
		}

		for (int i = 1; i <= n; i++){
			cin >> student[i];
			finish[student[i]]++;
		}

		for (int i = 1; i <= n; i++){
			int now = i;
			while (!check[now] && !finish[now]){
				ans++;
				check[now] = true;
				finish[student[now]]--;
				now = student[now];
			}
		}

		cout << ans << "\n";
	}
	return 0;
}

소스코드 : 방법 2

#include<iostream>
using namespace std;

int t, n, student[100001], stack[100001], check[100001], ans = 0;

void dfs(int now, int cnt){
	check[now]++;
	stack[cnt] = now;

	if (check[student[now]] == 0){
		dfs(student[now], cnt + 1);
	}
	else if (check[student[now]] == 1){
		bool iscycle = false;
		for (int i = 1; i <= cnt; i++){
			if (stack[i] == student[now]){
				for (int j = i; j <= cnt; j++){
					check[stack[j]]++;
				}
				ans += i - 1;
				iscycle = true;
				break;
			}
		}
		if (!iscycle)
			ans += cnt;
	}
	else{ // check[student[now]] == 2
		ans += cnt;
	}
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		ans = 0;
		for (int i = 1; i <= n; i++){
			cin >> student[i];
			check[i] = 0;
		}

		for (int i = 1; i <= n; i++){
			if (check[i] == 0){
				dfs(i, 1);
			}
		}

		cout << ans << "\n";
	}
	return 0;
}

소스코드 : 방법 3

#include <iostream>
using namespace std;
int t, n, student[100010], check[100010], team, cnt;

void dfs(int now, int start){
	if (check[now] > 0)
		return;

	check[now] = ++cnt;

	if (check[student[now]] >= check[start])
		team += cnt - check[student[now]] + 1;
	else
		dfs(student[now], start);
}

int main(void){
	freopen("text.txt", "r", stdin);
	cin >> t;
	while (t--){
		cin >> n;
		cnt = team = 0;
		for (int i = 1; i <= n; i++){
			check[i] = 0;
			cin >> student[i];
		}
		for (int i = 1; i <= n; i++)
			dfs(i, i);
		cout << n - team << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]