[Algorithm/C++17] 백준 1039 교환

문제

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

1039번: 교환

풀이 방법

문제에 설명되어있는 것처럼 i번 위치와 j번 위치를 바꾸는 연산을 K번 했을 때 나오는 수들의 최댓값을 구하면 된다. 헷갈릴 수 있는데, 탐색 과정 중의 최댓값을 구하는 게 아니라 탐색을 K번한 후의 최댓값을 구하는 것이다.

예를 들면 예제 입력2의 132 3에서 연산을 2번 했을 때의 수는 132, 213, 321이고 이 중 최댓값은 321이지만 연산을 3번 했을 때는 123, 231, 312로 최댓값은 312가 나온다.

그리고 132->123 , 123->132처럼 이전에 탐색했던 노드를 다시 방문할 수 있기 때문에, 탐색 depth마다 방문 여부를 초기화시켜줘야 한다.  

 

자릿수를 바꾸는 연산은 string이 다루기 쉽기 때문에 string을 사용했다.

방문 여부는 set을 사용하여 현재 string이 set에 포함되어 있으면 방문한 것이고, 없으면 방문을 하지 않은 것이다.

count는 탐색 depth를 나타낸다. 탐색을 queue의 size만큼 순회하면 현재 깊이의 노드를 모두 탐색한 것이므로 1만큼 증가시킨다.

 

코드

#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
    int N, K;
    scanf("%d %d", &N, &K);
    string str = to_string(N);
    size_t M = str.size();
    
    int answer = -1, count = 0;
    queue<string> q;
    q.push(str);
    while(!q.empty() && count < K) // 주어진 연산을 K번 한다.
    {
        set<string> visited;
        int qsize = q.size();
        while(qsize--)
        {
            string cur = q.front();
            q.pop();
            
            for(int i=0; i<M-1; i++)
            {
                for(int j=i+1; j<M; j++)
                {
                    if(i==0 && cur[j]=='0') continue; // 바꾼 수가 0으로 시작하면 안 된다.
                    // swap
                    string next = cur;
                    char tmp = next[i];
                    next[i] = next[j];
                    next[j] = tmp;
                    
                    if(visited.find(next) == visited.end())
                    {
                        if(count == K-1) answer = max(answer, stoi(next));
                        q.push(next);
                        visited.insert(next);
                    }
                }
            }
        }
        count++;
    }
    printf("%d", answer);
    return 0;
}

고찰

visited를 while문 안에서 지역변수로 사용하는 것이 아니라 밖에서 bool visited[1000001][10]으로 사용했다가, 메모리 사용량이 많아서 지금처럼 set<string>을 선언해주는 걸로 바꿨다.

그랬더니 메모리 사용량이 10분의 1 가량으로 줄어들었다.

 

또, queue의 size만큼 반복해주면 현재 depth의 노드를 모두 탐색하기 때문에 탐색 후에 count를 증가시켜주거나 하는 트릭이 가능하다.