[DFS] BJ16943 숫자 재배치

문제 출처: https://www.acmicpc.net/problem/16943

 

Solution

• DFS 탐색하며 A를 재배치해 나가고, A가 완성되면 B와 비교하여 조건을 만족하면 result를 업데이트 한다.

Point

• 주의할 점은 첫 번째 자리수에는 0이 올 수 없다는 점이다. 처음에 단순히 0만 스킵했다가 틀렸다.
• 이런 탐색 문제에서 실수하기 쉬운게 롤백하는 부분이다. DFS 리턴할 때는 visit과 값을 모두 반드시 롤백해줘야 한다.

---

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

using namespace std;

int A, B;
vector<int> alist;
int visit[10];
int result = 0;
bool possible = false;

void input() {
    cin >> A >> B;
    int n = A;
    while (n > 0) {
        int t = n % 10;
        n /= 10;
        alist.push_back(t);
    }
}

void dfs(int cur, int d) {
    if (d == alist.size()) {
        if (cur <= B) {
            result = max(result, cur); 
            possible = true;
        }
        return;
    }
    for (int i = 0; i < alist.size(); i++) {
        if (d == 0 && alist[i] == 0) continue; //0 can not be located at the first digit
        if (!visit[i]) {
            int tmp = cur;
            cur = cur * 10 + alist[i];
            visit[i] = true;
            dfs(cur, d + 1);
            visit[i] = false;
            cur = tmp;
        }
    }
}

int main() {
    input();
    dfs(0, 0);
    if(possible) cout << result;
    else cout << -1 << endl;
}