[백준] 1039번: 교환

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

1039번: 교환

 

1. 풀이 방법 

 

간단해보이지만 생각보다 꽤 까다로웠다. 구글링을 해보니 이 문제에 대해서는 BFS 풀이가 많았다.

그러나 DFS로도 풀렸다. DFS는 BFS에 비해 코드길이가 짧다는 장점이 있다! (큐를 구현해주지 않아도 되기 때문에...)

 

내가 생각한 로직은 다음과 같다. 

 

우선, dp 라는 이름의 배열의 요소들을 main 함수에서 전부 -1로 초기화를 할 것이다.

 

그 다음, DFS 함수를 구현할 것인데, DFS 함수의 매개인자로 문자열 a 와 정수형 depth을 받도록 선언한다.

첫 번째 수와 0이라는 수를 바꾸는 경우를 제외하고 모든 경우에 있어서 문자열의 서로 다른 두 문자를 스왑해준다.

단, 스왑을 할때마다 DFS 함수를 재귀호출해주면서, depth(깊이)가 원하는 목표(K)에 도달할때까지 DFS를 해준다.

마치 뿌리 끝까지 뻗어나가면서 찾아가는 방식이라고 생각하면 된다. 

이때, 만약에 depth가 K에 도달한다면 문자열 a를 stoi 함수를 사용하여 정수로 변환 후 return 해주므로, 

최댓값이 계속 갱신이 될 것이고, 최댓값 갱신이 안된다면 -1을 출력하게 된다.

 

2. 소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

string N;
int K;
int dp[1000001][11];

int DFS(string a, int depth) {
    if (depth == K) {
        return stoi(a);
    }
    // 참조변수  ret 선언
    int& ret = dp[stoi(a)][depth];

    // dp 배열 안의 값이 -1아니라면 그 값(아마도 최댓값)을 리턴해줌
    if (ret != -1) return ret;

    for (int i = 0; i < a.size(); i++)
    {
        for (int j = i + 1; j < a.size(); j++)
        {
            // 첫번째 수와 0이라는 수를 바꿀 경우는 그냥 무시하고 지나간다.
            if (a[j] == '0' && i == 0)    continue;
            swap(a[i], a[j]);
            // 바뀌기 전의 a문자열과 depth의 dp값, 바뀌고 난 후의 a문자열과 depth+1한 dp의 값의 DFS 결과를 비교해서 큰 값을 ret에 저장
            ret = max(ret, DFS(a, depth + 1));
            // 다시 원래대로 돌려준다. for문 반복을 해야하기 때문에.
            swap(a[i], a[j]);
        }
    }
    // 위 과정이 끝나면 ret을 return해줌 (그냥 계속 -1이 될수도 있고, 최댓값이 나올 수도 있음)
    return ret;
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> K;
    memset(dp, -1, sizeof(dp));
    cout << DFS(N, 0);

    return 0;
}