백준 2668 숫자고르기 c++ (dfs)

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

2668번: 숫자고르기

문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

풀이

조금 새로운 그래프 탐색 문제이다.

주어진 예시만 보고, 그냥 2중 for문 돌려도 될러나? 하고 돌려봤는데 아니나 다를까 주어진 예제만 통과된다.

이 문제가 dfs(깊이 우선 탐색)인 이유는, 

3

3 1 2

의 입력을 생각하면 된다.

1	2	3
3	1	2

위의 그래프를 보면, 1 -> 3 -> 2 -> 1 순으로 이동한다.

즉 인덱스 i -> 인덱스 i의 엘리먼트 -> 인덱스(인덱스 i의 멜리먼트) -> 인덱스(인덱스 i의 엘리먼트)의 엘리먼트 ->~~~

의 흐름으로 탐색을 하다 보면, 방문했던 숫자에 다시 방문하게 되는 경우가 발생한다.

이 경우, 인덱스1 에서 시작했는데 다시 인덱스1로 돌아온 경우는 방문한 인덱스의 숫자들과, 방문한 엘리먼트의 숫자들의 리스트가 같다는 의미로, 뽑을 수 있는 숫자들이다. 

1	2	3	4	5
3	1	2	5	5

위와 같은 경우도 있을 수 있기에, 모든 인덱스에서 dfs를 돌려봐야 한다.

 

풀이를 정리하면 다음과 같다.

1. 인덱스 1부터 n까지 dfs를 돌린다.

2. 인덱스 i에서 dfs로 탐색하여 방문했던 숫자에 다시 방문했을 때, 다시 i로 돌아왔는지 검사한다.

3. 다시 i로 돌아왔다면 플래그를 true로 바꿔, 재귀로 방문한 숫자들을 set에 삽입한다.

4. 다시 i로 돌아오지 않았다면 아무것도 하지 않고 return한다.

 

코드

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


//1<=n<=100
int n;
int input[101];
bool visited[101];
set<int> answer;
bool isRight;
void dfs(int firstNum,int num) {	
	if (visited[num]) {
		if (firstNum == num) {
				isRight = true;
				answer.insert(num);
		}
		return;
	}
	visited[num] = true;
	dfs(firstNum,input[num]);
	if (isRight) {
		answer.insert(num);
		answer.insert(input[num]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> input[i];
	}
	for (int i = 1; i <= n; i++) {
		visited[i] = true;
		dfs(i,input[i]);
		memset(visited, false, 101);
		isRight = false;
	}
	cout << answer.size() << '\n';
	for (auto o : answer) {
		cout << o << '\n';
	}
	return 0;
}