[C/C++] 백준 - 2668번 : 숫자 고르기

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)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

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

 

index와 value가 같은 수들로 이루어져있는 집합의 개수를 구하고, 그 index를 오름차순으로 정렬해서 출력하면 되는 문제이다. 나는 1부터 입력한 N까지 DFS를 하나하나 돌며 싸이클이 존재할 때까지 그때의 index와 value를 각각 다른 큐에 넣어두었다. 그리고 싸이클이 발견되었을 때 2개의 큐 안에 수들이 모두 같은 수로 이루어져있는지 확인해주는 방식으로 짰다. 이렇게 생각하고 코드를 짜는건 어렵지 않았으나 각 인덱스 DFS가 끝났을 때 큐를 비워주는 걸 까먹어서 이거 오류 고치는것만 30분 걸린것같다.ㅜ

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

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

int N, cnt; bool flag;
bool visited[105];
bool checked[105];
int Num[105];

queue<int> q;
queue<int> n_idx;
priority_queue<int> Answer;

void DFS(int idx) {
	visited[idx] = true;
	// n_idx 는 index값에 해당
	n_idx.push(idx);
	// q는 value값에 해당
	q.push(Num[idx]);

	// visited[Num[idx]]가 true라는 것은 전에 방문했던 곳을 다시 재방문한다는 뜻 -> 싸이클에 되돌아옴
	if (visited[Num[idx]] == true) {
		while (!q.empty()) {
			// q에 들어가있는 값들을 checked 배열에서 true로 바꿔줌
			int x = q.front(); q.pop();
			checked[x] = true;
		}

		while (!n_idx.empty()) {
			int x = n_idx.front(); n_idx.pop();
			// n_idx에 들어가있는 값이 checked 배열에서 false인 경우 index와 value가 다른 집합을 의미
			if (checked[x] == false) {
				flag = true;
				break;
			}
		}
		return;
	}

	DFS(Num[idx]);
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> Num[i];
	for (int i = 1; i <= N; i++) {
		// idx와 value가 같은 경우 굳이 DFS로 안들어가도 사이클을 가지므로 cnt+1, Answer pq에 푸쉬
		if (i == Num[i]) {
			cnt++;
			Answer.push(-i);
			continue;
		}
		memset(visited, false, sizeof(visited));
		memset(checked, false, sizeof(checked));
		flag = false;
		DFS(i);
		// DFS함수 내에서 flag가 true라는 것은 idx와 val이 다른 집합을 의미하므로 false일 때만 개수 증가 및 idx를 우선순위 큐에 푸쉬
		if (!flag) {
			cnt++;
			Answer.push(-i);
		}
		if (q.size() != 0) while (!q.empty()) { q.pop(); }
		if (n_idx.size() != 0) while (!n_idx.empty()) { n_idx.pop(); }
	}
	cout << cnt << "\n";
	while (!Answer.empty()) {
		int ans = Answer.top();
		Answer.pop();
		cout << -ans << "\n";
	}

	return 0;
}