[백준 1039번] 교환
백준에서 풀만한 문제가 뭐가 있다 어슬렁거리다 과거의 내가 풀지 못했던 문제를 지금 내가 푼다면 맞출 수 있을까 궁금해졌다. 슬프게도 시도했지만 맞지 못한 문제가 많아 숫자가 작은 것부터 다시 시도해 봤다. 그래서 선택한 1039번!!
무려 9년 전, 그러니까 2014년에 시도하고, 2015년에 다시 한번 시도하고 나에게 잊혔던 1039번이 다시 나에게 다가왔다. 과연 지금의 나는 과거의 나보다 더 강해졌을까 긴장되는 마음으로 문제를 다시 읽어봤는데 다행히 과거의 나보다는 더 강해진 것 같아 이렇게 풀이를 작성해 본다.
문제 링크
https://www.acmicpc.net/problem/1039
문제 요약
주어진 정수 \(N\)에서 서로 다른 두 자릿수의 위치 \(i\), \(j\)를 선택하여 숫자를 서로 교환하는 연산을 정확히 \(K\)번 수행할 때, 가능한 최댓값을 구하는 문제이다.
문제 풀이
문제를 풀기 전에 꼭 알아야 할 세 가지 주의사항이 있다.
- 정확하게 \(K\)번을 연산한 뒤 나올 수 있는 최댓값을 찾아야 한다. 연산 횟수가 \(K\)번보다 적어도 안되고 \(K\)번보다 많아도 안된다.
- 연산 과정 속에서 나오는 숫자는 0으로 시작할 수 없다.
- \(K\)번 연산을 수행할 수 없으면 -1을 출력해야 한다.
주의사항 세 가지를 알아봤으니 이제는 본격적인 풀이를 알아보자. 현재 수 \(here\)과 남은 연산 횟수 \(left\)의 쌍을 하나의 독립적인 상태로 보고 노드라고 생각하면 DFS 혹은 BFS를 이용해 쉽게 문제를 풀 수 있다. 개인적으로 BFS 보다는 재귀를 사용하는 DFS가 더 멋있어 보여서 DFS로 풀었다.
일반적으로 그래프의 순회 알고리즘을 구현할 때 노드의 방문 여부를 배열로 확인하곤 하지만, 이 이 문제에서는 가능한 노드의 수가 \(len(N)! * K\)로 많지 않기 때문에 메모리를 아끼기 위해 \(set\)을 사용해 구현했다.
서로 다른 두 자릿수를 교환하는 연산은 직접 구현해도 되고 언어에서 제공하는 라이브러리를 사용해도 좋다. 나는 C++에서 제공하는 \(\text{to_string}\)과 \(\text{stoi}\)를 이용해 구현했다.
마지막으로 최댓값을 찾을 때 구현 편의상 재귀함수의 기저사례에서 최댓값을 찾는 로직을 넣었다.
소스 코드
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
int n, k, ans = -1;
set<pair<int, int>> visited;
void dfs(int here, int depth) {
if (depth == 0) {
ans = max(ans, here);
return;
}
visited.insert({ here, depth });
string str = to_string(here);
for (int i = 0 ; i < str.size() ; ++i) {
for (int j = i + 1 ; j < str.size() ; ++j) {
swap(str[i], str[j]);
if (str[0] != '0') {
const int there = stoi(str);
if (!visited.count({ there, depth - 1 })) {
dfs(there, depth - 1);
}
}
swap(str[i], str[j]);
}
}
}
int main() {
cin >> n >> k;
dfs(n, k);
cout << ans << endl;
}