[DFS] 10597번 순열 장난

10597번 순열장난

 

https://www.acmicpc.net/problem/10597

 

문제

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

 

입력

첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

 

출력

복구된 수열을 출력한다. 공백을 잊으면 안된다.

복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

 

예제 입력

4111109876532

155987643211011121314

 

예제 출력

4 1 11 10 9 8 7 6 5 3 2

15 5 9 8 7 6 4 3 2 1 10 11 12 13 14

 

해결방법

DFS + 백트래킹을 통해 완전탐색하는 문제이다

정말 많이 해맸다….흑

 

⭐️ 1차 시도 ⭐️

런타임 에러

 

처음 접근법은 아래와 같다

• 입력받은 순열의 첫번째 인덱스부터 DFS 탐색을 수행한다
• 만약 visited 배열에 없는 수라면 순열에 포함시킨다
• 반대로 이미 중복된 수라면 tmp 스트링에 더해준다

 

하지만 이렇게 진행된 코드는 문제의 조건에 어긋나게 된다

3자리의 수가 탐색되는 경우를 처리해주지 못하기 때문에 컴파일 에러가 발생했다

void dfs(int cnt){
    if(cnt > len){
        return;
    }
    
    // 마지막 순열까지 탐색 완료했다면
    if(cnt == len){
        for(int i=0; i<v.size(); i++){
            cout << v[i] << " ";
        }
        cout << "\n";
        exit(0);
    }
    
    // DFS 탐색 수행
    int num = stoi(tmp + str[cnt]);
    
    // 만약 순열에 포함할 수 있는 수라면
    if(visited[num] == 0){
        tmp = "0";
        
        visited[num] = 1;
        v.push_back(num);
        dfs(cnt+1);
        v.pop_back();
        visited[num] = 0;
    }
    // 이미 중복된 수라면
    else{
        tmp += to_string(num);
        dfs(cnt+1);
    }
}

 

 

 

⭐️ 2차 시도 ⭐️

틀렸습니다

 

블로그를 보고 새로운 방법을 발견했다

순열의 1자리 또는 2자리를 탐색하는 방법이다

 

하지만 어떤 예외의 경우가 존재하는지 틀렸습니다가 나왔다

void dfs(int ind,int cnt){
    if(cnt > len) return;
    
    // 마지막 순열까지 탐색 완료했다면
    if(cnt == len){
        for(int i=0; i<v.size(); i++){
            cout << v[i] << " ";
        }
        cout << "\n";
        exit(0);
    }
    
    string d = "";
    for(int i=ind; i<ind+2; i++){
        d += str[i];
        int dtoi = stoi(d);
        
        if(!visited[dtoi]){
            v.push_back(dtoi);
            visited[dtoi] = true;
            dfs(i+1, cnt+(int)d.size());
            visited[dtoi] = false;
            v.pop_back();
        }
    }
}

 

 

⭐️ 3차 시도 ⭐️

맞았습니다!!

 

예외의 테스트케이스를 찾지 못하던 중, 새로운 테스트 케이스를 발견했다

155987643211011121314

15 5 9 8 7 6 4 3 2 1 10 11 12 13 14

 

이런 경우에 나의 코드에서는 아래와 같은 결과가 나왔다

1 5 59 8 7 6 4 3 2 1 10 11 12 13 14

 

즉 최대 N의 값이 50인데 MAX_VALUE 값을 처리해주지 않은 것이다!!

따라서 입력받은 순열을 기반으로 최대 값을 찾아주는 코드를 작성해야했다

 

• 만약 순열이 10보다 작으면 이는 1자리 숫자로만 구성된 순열이다
• 따라서 MAX_VALUE 는 순열의 길이와 같다
• 10보다 크다면 1자리수의 개수와 2자리수의 개수를 더해야 한다
• 따라서 MAX_VALUE 는 1자리수(9개) + 2자리수(len-9 / 2) 이다

 

if(len < 10){
    max_value = len;
}else{
    max_value = (len - 9) / 2 + 9;
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 51
#define INF 987654321
using namespace std;

int len,max_value;
string permutationWithoutSpace;

bool visited[MAX];
vector<int> v;

void dfs(int ind){
    // 정상적으로 순열을 나눈 경우
    if(ind == len){
        for(int i=0; i<v.size(); i++){
            cout << v[i] << " ";
        }
        cout << "\n";
        exit(0);
    }
    
    // 순열을 1자리 또는 2자리로 자름
    string p = "";
    int ptoi = 0;
    for(int i=ind; i<=ind+1; i++){
        p += permutationWithoutSpace[i];
        ptoi = stoi(p);
        
        if(ptoi > max_value) continue;
        if(visited[ptoi]) continue;
        
        v.push_back(ptoi);
        visited[ptoi] = true;
        dfs(i+1);
        visited[ptoi] = false;
        v.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> permutationWithoutSpace;
    
    // 순열의 길이와 최대값을 구함
    len = (int) permutationWithoutSpace.size();
    
    if(len < 10){
        max_value = len;
    }else{
        max_value = (len - 9) / 2 + 9;
    }
    
    memset(visited, false, sizeof(visited));
    dfs(0);
    
    return 0;
}