[백준] 9466번 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

풀이 방식이 어떻게 보면 꼼수일 수도 있는 것 같은데 이전과 비교하면 메모리와 시간을 굉장히 많이 단축해서 뿌듯해서 올려본다.

 

변수

배열 board - n개의 선택된 학생들의 번호가 저장

배열 vis     - n명의 학생들에 대해 선택 여부 저장

변수 result - 결과값 (프로젝트 팀에 속하지 못한 학생들의 수)

큐 q - BFS에서 사이클을 확인하는 데 사용됨

 

알고리즘 방식

* 데이터를 입력받을 때 자기 자신을 가르키는 경우 result-- 와 vis를 1로 만들어준다.

* BFS를 변형해서 사용했는데

1. 1부터 n까지 i가 증가할때 vis[i] == 0인 경우에 BFS를 실행

2.. cur = board[i]로 하여 i가 가리키는 값을 cur에 저장

이때 vis[cur]에 대하여

3-1. vis[cur] == 0 인 경우는 사이클이 이어질 수 있으므로 q.push(cur)을 통해 반복문 지속

      + vis[cur] = 1로 바꿔준다.

3-2. vis[cur] == 1 인 경우는 다시 2가지 경우로 나뉜다.

                     a. 같은 사이클에 있는 경우  b. 다른 사이클에 있는 경우

     3-2-1. a인지 b인지 확인하기 위해 지금까지 q에 들어간 데이터들을 하나씩 pop 하여 

             vis[cur] == 1일 때의 cur값과 같은지 확인한다.(같은 게 나오면 a. 의 경우 아니면 b.)

     3-2-2. 같은 값이 나오면 그 숫자를 기점으로 q에 들어있는 다른 숫자들도 함께 사이클을 이루고 있는 숫자라는 의미

              따라서 result--를 큐가 비어질때 까지 반복한다.

              (q가 비어질때까지 같은 값이 안 나온다면 사이클을 구성하지 못했다는 의미이다.)

 

내가 써놓긴했는데 너무 어렵게 써놓은 것 같기도 하고.... 설명해놓는 게 쉽지 않네...

나중에 나도 이해 못할 것 같다. 다시 보게 되면 그때 고쳐야겠다. 지금은 어떻게 더 자세하게 해야 되는지 감이 안 온다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int T, n, result;
int board[100001];
int vis[100001];
queue<int> q;

void BFS() {

	for (int i = 1; i <= n; i++) {

		if (vis[i] == 0) {
			q.push(i);
			vis[i] = 1;
			int cur = board[q.front()];

			while (!q.empty()) {				
				bool find = false;
                
				if (vis[cur] == 1) {	
                
					while (!q.empty()) {
                    
						if (q.front() == cur)
							find = true;
                            
						if (find == true)
							result--;
                            
						q.pop();
					}
				}

				else { // vis[cur] == 0)
					q.push(cur);
					vis[cur] = 1;
					cur = board[cur];
				}
			}
		}
	}
}

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

	cin >> T;

	while (T--) {
		cin >> n;
		result = n;
		fill(&vis[0], &vis[100001], 0);
		//memset(vis, 0, sizeof(vis));
        
		for (int i = 1; i <= n; i++) {
			cin >> board[i];
            
			if (board[i] == i) {
				result--;
				vis[i] = 1;
			}				
		}		

		BFS();
		
		cout << result << '\n';
	}	
}