[BOJ] 2668번 : 숫자고르기(C++)

프로그래머스 백엔드 데브매칭 준비하느라 Go로 풀었었는데 네이버 공채는 Go를 지원하지 않아서 다시 c++로 연습한다.

---

문제 링크 : 백준 2668번

[문제 접근]

N의 크기가 100밖에 되지 않아서 재귀를 통해 완전탐색하면 될 것 같았다.

1. i번에서 시작해서 마지막에 i번으로 돌아오면 -> 즉, 사이클이면 뽑으면 된다.
2. result에 시작값을 넣고 재귀를 돌면서 visit를 true로 채워준다.
3. i번으로 절대 돌아올 수 없으면 false를 리턴하면서 visit를 false로 바꿔주고 함수가 끝난다.(백트래킹 느낌으로..?)
4. i번으로 돌오면 사이클이므로 그대로 true를 리턴해 visit는 true인 상태로 함수가 끝난다.
5. 최종적으로 visit가 true인 값들이 정답이다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;
int n;
int arr[101];
bool visit[101];

bool go(int num, int result) {
    if(arr[num] == result) {
        visit[num] = true;
        return true;
    } else {
        if (!visit[num]) {
            visit[num] = true;
            if(go(arr[num], result)) {
                return true;
            } else {
                visit[num] = false;
                return false;
            }
        } else {
            return false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        cin >> arr[i];
    }
    for(int i=1 ; i<=n ; i++) {
        go(i, i);
    }
    int cnt=0;
    for(int i=1 ; i<=n ; i++) {
        if (visit[i]) cnt++;
    }
    cout << cnt << "\n";
    for(int i=1 ; i<=n ; i++) {
        if(visit[i]) cout << i << "\n";
    }
}