Baekjoon 1039번 교환

문제

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

걸린 시간

01 : 07 : 17

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

string N;
int K;
map<pair<string, int>, int> visited; // key : n, k

int bfs(){
    queue<string> q;
    q.push(N);
    int ans = -1;
    int depth = -1;
    while(!q.empty()){
        depth++;
        int size = q.size();
        for(int c = 0; c < size; c++){
            string here = q.front();
            q.pop();
            if(depth == K){
                ans = max(ans, stoi(here));
                continue;
            }
            for(int i = 0; i < N.size(); i++){
                for(int j = i+1; j < N.size(); j++){
                    string next = here;
                    char tmp = next[i];
                    next[i] = next[j];
                    next[j] = tmp;
                    if(next[0] == '0') continue;
                    if(visited[make_pair(next, depth)] != 0) continue;
                    visited[make_pair(next, depth)] = 1;
                    q.push(next);
                }
            }
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    cout << bfs(); 
    return 0;
}

완전탐색으로 정답을 구해본 후 어떻게 최적화를 시킬지 고민하다 바꾼 숫자의 인덱스 i, j 와 지금까지 바꾼 횟수 k 값으로 메모이제이션을 적용해 보았는데 생각이 너무 짧았던 것 같다.

분류를 보니 그래프 탐색 문제였다. 문자 두개를 바꾸는 작업을 방문 배열을 사용해서 중복되지 않게 k번 반복해야한다. bfs, dfs 원리는 모두 같으므로 둘 중 아무거나 사용하면 될 것 같다. visited 배열의 key 값이 조금 특이해서 골드 3 문제이지 않았나 싶다.