백준 10451 순열사이클

이 문제의 특징은 '어떠한 노드 s를 목적지로 하는 노드는 1개, 이 s 노드에서 시작하는 노드도 1개'라는 것이다.

이걸 전문용어로 뭐라 있을거 같은데 흠..

여튼, 그렇기 때문에 bfs같은 탐색을 할 필요 없이 선형으로 탐색하면 된다.

첫번째 반복문은 아직 탐색하지 않은 루트 노드를 선택하는데 쓰고

두번째 반복문은 이 노드로부터 시작하는 사이클을 찾는데 쓴다

탐색을 하다가 이미 방문한 노드를 발견하면 주저없이 반복문을 끝내고 사이클의 갯수를 1증가 시키면 된다.

왜냐하면 위에서 말한 특징 때문에 '이미 탐색한 노드 x를 지금 탐색하였다면 그 x노드는 탐색을 시작했던 노드'라는 명제가 성립하기 때문.

main.cpp

#include <iostream> 
#include <vector> 
#include <queue> 
#include <fstream> 
#include <string> 
#include <algorithm>
using namespace std;

int numlist[1001];
int isVisit[1001];
int testcase;
int N;

int main() {
	cin >> testcase;
	while (testcase--) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> numlist[i];
			numlist[i]--;
			isVisit[i] = false;
		}
		int graphNum = 0;
		for (int i = 0; i < N; i++) {
			if (isVisit[i] == false) {
				int now = i;
				isVisit[now] = true;
				while (true) {
					int next = numlist[now];
					if (isVisit[next] == false) {
						isVisit[next] = true;
						now = next;
					}
					else {
						graphNum++;
						break;
					}
				}
			}
		}
		cout << graphNum << endl;
	}

	return 0;
}

이것으로 튜토리얼중 BFS문제는 다 풀었당