#2668번 숫자고르기 (C++)

링크 : www.acmicpc.net/problem/2668

2668번: 숫자고르기

이 문제는 먼저 유의 사항을 파악해야하는데,

문제에 제시된 테스트 케이스 외에 아래 케이스도 이해해야한다. 

 

입력값

3
3
1
2

출력값

3
1
2
3

1	2	3
3	1	2

나는 초반에 무조건 쌍을 이루어서, 그러니까 (1,3)과 (3,1)이 짝을 이루어서 존재해야만 문제가 풀릴 것으로 착각했고

그 결과 아무리 채점을 해도 오답이 나오는 현상을 겪게되었다. 

정말 당연하지만 (1,3) (3,1)과 같은 구성만 인정된다면 이 문제는 굳이 DFS까지 구현하지 않아도 for문을 통해 풀 수 있다.

 

이해가 안간다는 질문을 올린 뒤, 다른 분이 해당 케이스를 통해 놓친 부분을 발견해주신 덕분에 무엇이 잘못되었는지 알게되었다. 

회귀 구조

이렇게 처음 입력값으로 돌아오게 될 경우, 그동안 거쳐왔었던 값들이 중복되지 않도록 누적해줘야 하는데 

이 점에서 또 오랜 시간이 걸렸다. 

 

결론적으로 문제풀이는 다음과 같다.

 

(1) 1부터 N까지 for문을 돌린다. 해당 값을 방문한 적이 없을 경우(false), DFS를 진행한다.

진행도 : 1

(2) 배열 1의 값은 3인데, 해당 값을 방문한 적으므로 DFS를 진행한다.

진행도 : 1 -> 3 

(3) 3의 값은 2인데, 해당 값을 방문한 적이 없으므로 DFS를 진행한다. 

진행도 : 1 -> 3 -> 2

(4) 2의 값은 1이다. 이미 방문한 경험이 있으므로, if가 아닌 else if로 배열 2의 값 '1'로 끝맺음(fin 배열)을 한 적이 있는지를 체크한다.

진행도 : 1-> 3-> 2 -> 1(방문경험이 있다)

(5) 끝맺음은 별도의 fin배열로 확인한다. 끝을 맺은적이 없는 경우(false), 해당 값을 넣어준다.

또한 for문을 이용해 누적된 값을 정답 배열에 넣어준다.

 

for(int i=arr[a]; i!=a; i=arr[i])

이 for문이 이해안갈수도 있는데, 결국 넣게 되는 값들은 다음과 같다.

arr[0] = 2 // arr[2] = 1

arr[1] = 1 //arr[1] = 2

arr[2] = 3 // arr[3] = 1

arr[3] = 2인데, i!=a 조건 때문에 입력되지 않는다.

 

(6) else if를 빠져나와 DFS가 종료되면서, 순서대로 2 -> 3 -> 1로 빠져나오며 fin[2] -> fin[3] -> fin[1]이 true로 변경된다. 이로인해 만약 다른 배열에서 중복된 값을 가져도 값이 추가될 일을 방지하게 된다. 

(7) 배열은 정렬해주고 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 0, cnt = 0;
int arr[101];
bool check[101];
bool fin[101];
int ans[101];

void dfs(int a) {
    check[a] = true;
    if (!check[arr[a]]) dfs(arr[a]);
    else if (!fin[arr[a]]) {
        ans[cnt++] = a;
        for (int i = arr[a]; i != a; i = arr[i]) ans[cnt++] = i;
    }
    fin[a] = true;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    for (int i = 1; i <= n; i++) {
        if (!check[i]) dfs(i);
    }
    cout << cnt << "\n";
    sort(ans, ans + cnt);
    for (int i = 0; i < cnt; i++) cout << ans[i] << "\n";

    return 0;
}

문제를 잘못 이해한덕에 한참 헤맸다.