[Algorithm/C++17] 백준 10597 순열장난

문제

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

10597번: 순열장난

풀이 방법

한 자릿수 또는 두 자릿수로 끊어 공백을 만들고, 만들어진 수열의 길이가 N일 경우 출력하는 문제이다.

공백으로 분리한 수를 이미 사용했으면 더 진행하지 않고 멈추는 가지치기와 실행했던 과정을 되돌리는 백트래킹을 사용한다. 주의할 점은 성공 케이스에서 조건비교인데, 아래 코드처럼 수열의 개수로 해도 되고 다른 풀이처럼 만들어진 수열의 가장 큰 수로 비교해도 된다.

코드

#include <cstdio>
#include <string>
#include <vector>
using namespace std;
bool success = false;
int used[52] = {0,};
vector<int> result;
void solve(string &s, int n, int pos, int len)
{
    // 성공 케이스
    // 1부터 len까지의 수열이 만들어짐
    if(n==len) 
    {
        for(int i=0; i<result.size(); i++)
        {
            printf("%d ", result[i]);
        }
        success = true;
        return;
    }
    // 한 자리수 
    int num = s[pos]-'0';
    if(num > 0 && !used[num] && !success)
    {
    	// 공백으로 한 자리수를 끊어 탐색을 진행해본다.
        used[num] = 1;
        result.push_back(num);
        solve(s, n+1, pos+1, len);
        // 탐색이 끝난 후 진행 과정을 되돌린다.
        used[num] = 0;
        result.pop_back();
    }
    // 두 자리수
    if(pos+1 >= s.size()) return; // 바운더리 체크
    num = num*10 + s[pos+1]-'0';
    if(num < 51 && !used[num] && !success)
    {
    	// 공백으로 두 자리수를 끊어 탐색을 진행해본다.
        used[num]=1;
        result.push_back(num);
        solve(s, n+1, pos+2, len);
        // 탐색이 끝난 후 진행 과정을 되돌린다.
        used[num] = 0;
        result.pop_back();
    }
    
}
int main()
{
    char str[100];
    scanf("%s", str);
    // 필요한 수열 개수 구하기
    int len = 0;
    for(int pos=0; str[pos];)
    {
        len++;
        if(len >= 10) pos +=2;
        else pos += 1;
    }
    string s(str);
    // 탐색 종료 조건을 문자열의 길이인 s.size()가 아니라
    // 수열의 개수로 해줘야한다.
    solve(s, 0, 0, len);
    return 0;
}

고찰

백트래킹 알고리즘이 익숙하지 않아서 좀 어려웠다.

백트래킹 과정은 다음과 같이 진행된다.

1. 방문 표시
2. 방문한 노드에서 더 깊게 탐색
3. 탐색한 결과가 성공 케이스일 경우 출력
4. 탐색이 끝난 후 방문 표시 해제

이를 의사코드에 가까운 단순한 코드로 하면 

bool success = false;
void find(int idx)
{
    if(idx == n) // 3
    {
    	success = true;
    	return;
    }
    visited[idx] = true; // 1
    find(idx+1); // 2
    visited[idx] = false; // 4
}

이렇게 되는데 처음엔 어디서 결과를 출력해야 하고 방문 표시를 되돌려야 하는지 헷갈렸다.

곰곰이 생각해보면 방문 표시를 하고 함수를 재귀적으로 호출하기 때문에, 호출된 함수가 계속해서 if문의 성공케이스까지 도달했다면 풀이가 완료되었다고 보고 출력하면 된다. 만약 도달하지 못했다면 반환되면서 방문 표시를 계속 되돌린다. 

말로 하니 좀 어려운데 현재 상태를 노드로 갖고 있는 그래프로 함수 호출 과정을 생각하면 좀 더 이해하기 쉬울 듯 하다.