[백준] 2668번: 숫자고르기 with unique DFS

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

2668번: 숫자고르기

오랜만에 PS 하는데 헤맸다...ㅠㅡㅜ

우선 이게 DFS로 풀면 쉬운 문제라는 사실을 인지하지 못했다.

처음에 시도한 방법은 크게 2가지이다.

 

1) 다이나믹 프로그래밍

i개의 칸을 이용해 만든 조합에 덧대면 되지 않을까?

→ 실패

→ 왜냐하면 이전 칸 중 해당 조합에 포함되지 않은 칸을 포함해야 최대가 되는 경우는? 모두 꼬인다..

반례)

3/4/5/2/1

만약 내 식대로 문제를 풀면 2와 4를 포함하는 게 답으로 나와버린다.

사실 맨 뒤의 1을 포함해서 1,2,3,4,5 모두 조합하면 최대가 나올 수 있다.

 

2) 브루트포스

답답한 마음에 해당 칸을 포함하느냐 마느냐의 문제로 간단하게 생각해보기 시작했다.

문제는 명확하게 풀리나, 당연하게도 시간초과가 발생한다.

시간제한은 1초이라 시간복잡도 상으로 1억이라고 가정한다면, $2^100$으로 택도 없는 시간 복잡도가 발생한다.

 

이 문제를 효율적으로 풀기 위해서는 세로 두줄을 구분을 줄이고, 1 → 3 → 3 → 1 들이 각각 하나의 방문점이라고 생각하면 된다.

그래서 만약 중복된 숫자가 발견되었는데(사이클 발견), 첫번째 시작과 동일한 경우에는 원하는 조합이 발생한 것이다.

 

이러한 조합들을 합하면 정답이 도출된다.

 

으 이걸 왜 생각 못했을까...

예상치 못했던 DFS 문제라 더욱 유익하다고 느낀 문제 풀이였다.

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int maxcnt = 0;
set<int> result;
void go(int idx, int first_idx, set<int> &s, vector<bool> &visited, vector<int> &nums) {
	if(!visited[idx]) {
		int next_idx = nums[idx];
		s.insert(idx);
		visited[idx] = true;
		go(next_idx, first_idx, s, visited, nums);
	}
	else {
		if(idx == first_idx) {
			for (auto num : s) {
				result.insert(num);
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> nums(n + 1);
	for(int i = 1;i <= n;i++) {
		cin >> nums[i];
	}

	for(int i = 1;i <= n;i++) {
		vector<bool> visited(n + 1, false);
		set<int> s;
		go(i, i, s, visited, nums);
	}

	cout << result.size() << '\n';
	for (auto num : result) {
		cout << num << '\n';
	}
}