BOJ 10597 - 순열장난 링크
(2023.04.14 기준 S1)

문제

1부터 N까지의 수로 이루어진 순열의 모든 공백을 지운 채로 주어질 때, 복구했을 때의 가능한 아무 순열 출력

알고리즘

백트래킹

풀이

백트래킹이 무엇인가? 간단히 설명하자면, 모든 경우의 수를 다 가보다가 여긴 아니다 싶으면 다시 되돌아가는 것이다. 마치 미로 찾기처럼 말이다.

이 문제도 똑같다. 먼저, 주어지는 순열의 길이를 보고 N을 찾자. 1부터 9까지는 길이가 1씩, 그 뒤로 50까지는 2씩 증가한다.

N을 찾았으면 백트래킹을 시작하자. 첫번째 수부터 하나씩 해보는 것이다.
조건은 다음과 같다.
1. N 이하인가?
2. 지금까지 저장된 수에 포함되지 않는가?
만약 지금 단계에서 가능한 모든 수가 조건에 부합하지 않는다면? 지금까지 왔던 미로의 루트는 틀린 것이다. 즉, 지금까지 저장해온 순열이 가능하지 않다는 것이다. 그러면 다시 한 단계 되돌아가서 다른 수로 시도해보는 것이다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

string permutation;
int sz, N, restore[50]; // 복구 순열
bool visited[51]; // 1부터 N까지의 수가 각각 나왔는지 체크

bool dfs(int i, int find){ // i는 살펴봐야 할 순열의 인덱스. find는 찾은 수의 개수

    // N개를 찾았다면 순열을 모두 복구한 것이므로 True 반환
    if (find == N) return true;

    // i번째 수부터 시작
    int n = permutation[i++] - '0';
    while (n <= N){ // 현재 수가 N보다 작아야 한다.

        // 현재 수가 나오지 않은 수이면 체크 및 저장 후 다음 수를 찾으러 가자.
        if (!visited[n]){
            visited[n] = true;
            restore[find] = n;
            if (dfs(i, find + 1)) return true; // 이 결과가 맞았다면 True 반환
            visited[n] = false; // 아니면 지금 순서에서 현재 수를 체크하면 안된다는 뜻이다.
        }

        // 다음에 살펴봐야 할 인덱스가 끝을 벗어난다면 break
        if (i == sz) break;

        // 다음 인덱스의 수를 합쳐주자.
        n *= 10;
        n += permutation[i++] - '0';
    }

    // 여기까지 True를 반환하지 못했다면 지금 저장되어 있는 복구 순열은 잘못된 것임을 뜻한다.
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> permutation;

    // 9까지는 순열의 길이가 1씩 늘어나고 그 뒤로 50까지는 2씩 늘어난다.
    sz = permutation.size();
    if (sz <= 9) N = sz;
    else N = (sz - 9) / 2 + 9;

    visited[0] = true; // 0이 들어가는 것을 방지
    dfs(0, 0);
    for (int i = 0; i < N; i++) cout << restore[i] << ' ';
}

• Python

import sys; input = sys.stdin.readline

def dfs(i, find): # i는 살펴봐야 할 순열의 인덱스. find는 찾은 수의 개수

    # N개를 찾았다면 순열을 모두 복구한 것이므로 True 반환
    if find == N:
        return True

    # i번째 수부터 시작
    n = permutation[i]
    i += 1
    while n <= N: # 현재 수가 N보다 작아야 한다.

        # 현재 수가 나오지 않은 수이면 체크 및 저장 후 다음 수를 찾으러 가자.
        if not visited[n]:
            visited[n] = True
            restore[find] = n
            if dfs(i, find + 1): # 이 결과가 맞았다면 True 반환
                return True
            visited[n] = False # 아니면 지금 순서에서 현재 수를 체크하면 안된다는 뜻이다.

        # 다음에 살펴봐야 할 인덱스가 끝을 벗어난다면 break
        if i == sz:
            break

        # 다음 인덱스의 수를 합쳐주자.
        n *= 10
        n += permutation[i]
        i += 1

    # 여기까지 True를 반환하지 못했다면 지금 저장되어 있는 복구 순열은 잘못된 것임을 뜻한다.
    return False

permutation = list(map(int, input().strip()))

# 9까지는 순열의 길이가 1씩 늘어나고 그 뒤로 50까지는 2씩 늘어난다.
sz = len(permutation)
if sz <= 9:
    N = sz
else:
    N = (sz - 9) // 2 + 9

restore = [0] * N # 복구 순열
visited = [False] * (N + 1) # 1부터 N까지의 수가 각각 나왔는지 체크
visited[0] = True # 0이 들어가는 것을 방지
dfs(0, 0)
print(*restore)