백준 10451. 순열 사이클 [성공]

1.문제 해결 전략

사이클의 개수를 파악하는 문제. 예전 강의를 들었을 때 유니온 파인드를 통해 쉽게 찾을 수 있다는 것을

배웠었지만 당장 그 구조를 떠오르지가 않아서 굉장히 날 것의 코딩을 통해 문제를 해결했다.

 

dfs를 베이스로 시작지점과 끝지점이 같을 때 하나의 사이클이 완성된다는 것을 이용하여

dfs 파라미터로 start,end를 넘기고 start == end일 때 사이클의 개수를 증가시켰다.

 

2.작성 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> v[1001];
bool visit[1001] = { false, };
int c = 0;
void dfs(int start, int end) {
	if (visit[start] == true)return;

	visit[start] = true;

	for (int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		if (next == end) {
			c++;
			return;
		}
		dfs(next, end);
	}
}

int main() {
	int T;
	int N;
	std::cin >> T;

	for (int i = 0; i < 1001; i++) {
		v[i].clear();
	}

	for (int i = 0; i < T; i++) {
		cin >> N;
		for (int j = 1; j <= N; j++) {
			int k = 0;
			cin >> k;
			v[j].push_back(k);
		}

		for (int j = 1; j <= N; j++) {
			if (visit[j] == false) {
				dfs(j, j);
			}
		}

		std::cout << c << std::endl;
		c = 0;
		for (int i = 1; i <= N; i++) {
			visit[i] = false;
		}
		for (int i = 0; i < 1001; i++) {
			v[i].clear();
		}
	}
}

3.걸린 시간 & 느낀점

15~20분 정도에 풀었다.

dfs의 구조는 굉장히 간단하니까 외우고 있어야겠다. 만약 한 두달 후 다시 그래프 문제를 풀게 됐을때

구조를 외우고있지 않는다면 풀지 못할 것이다.