[백준][2668][c++] 숫자고르기

숫자 고르기 문제 링크

[풀이]
이 문제에서 나올 수 있는 case들에 대해 먼저 정리하면 좋을 것이다
첫번째 줄을 index 라고 칭하고 두번째 줄은 value값이라고 놓았다.

case1) i -> i
case2) 1 -> 2 -> 3 -> 2
case3) 1 -> 2 -> 3 -> 1

case3처럼 cycle을 이루어야지 첫째 줄에서 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치하게 된다.

따라서, case 각각을 처리해주는 알고리즘을 만들기 위해, case1은 따로 입력을 받으면서 처리해준후 , 1~N까지 시작 원소를 하나 정해서 타고타고 들어가서 case2, case3 처리를 해주면 될 것이다.

[코드]

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#define N_MAX 101

using namespace std;

int N;
int arr[N_MAX];


int main() {
	vector<int> result;
	set<int> candidates;
	//result에 이미 들어간 숫자는 다시 탐색 안하고자 함
	bool checked[N_MAX] = { false, };
	cin >> N;

	//case1 처리
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		candidates.insert(arr[i]);
		if (i == arr[i]) {
			checked[i] = true;
			result.push_back(i);
		}
	}

	//두번째 줄에서 나온 숫자 종류 
	int can_size = candidates.size();
	
	
	for (int i = 1; i <= N; i++) {
		int cur = i;       //첫째줄
		int next = arr[i]; //두째줄
		
		//이미 다 찾았으면 break
		if (can_size == result.size()) break;

		//result에 이미 있음 즉 탐색 끝난 숫자들 check
		if (checked[cur]) continue;
		if (checked[next]) {
			continue;
		}

		//first에 첫째줄 원소, second에 두째줄 원소
		//넣어 둘이 동일한지 아닌지 체크하기 위함
		set<int> first;
		set<int> second;

		//시작 원소를 기점으로 타고타고 들어간 애들 check해주기 위함
		bool visited[N_MAX] = { false, };
		while (1) {
			first.insert(cur);
			second.insert(next);

			visited[cur] = true;
			if (first == second) {
				for (auto iter = first.begin(); iter!= first.end(); iter++) {
					checked[*iter] = true;
					result.push_back(*iter);
				}
				break;
			}
			
			cur = next;
			next = arr[cur];
			
			//case2 처리
			if (visited[next] & i != next) {
				break;
			}

		}
		
	}

	cout << result.size() << "\n";
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}


}

[총평]
while문 무한을 이용해서 타고타고 들어가서 코드가 복잡해 졌고, 오류를 알기 조금 어려워졌다. 그리고 case를 깔끔하게 안 나누고 시작해서 중간에 다시 짰다. 이렇게 푸는 것보다 타고타고 들어가는데 사용되는 dfs를 사용한다면 더 깔끔할 것이다.

[참고자료]
https://gusdnr69.tistory.com/46