[백준 1039번] [BFS] 교환

Approach

문제 설명이 난해해서 꽤 많이 틀렸다..

 

일단, 연산을 k번 했을 때의 상황을 묻는 것이므로 BFS문제임을 쉽게 직감할 수 있다.

기본적으로 다음 문제 컨셉과 비슷하기 때문이다. https://viyoung.tistory.com/338

[백준 9019번] [BFS] DSLR

이 문제가 좀 어려운 이유는 정확히 K번 움직였을 때 나올 수 있는 수들 중 최댓값을 구해야한다는 지점이다. 

왜냐하면 단순히 기존의 방문한 숫자를 다시 방문하지 않는 방식으로는 해결할 수 없기 때문이다. 예를 들어 1000 2의 경우, 정답이 1000이 나와야하는데 만약 1000을 방문처리해서 BFS를 할 때 큐에 넣지 않으면 이를 정답으로 출력할 수 없다.

 

사실 잘 생각해보면 단순히 큐에 넣지 않는 이유가 중복되는 숫자들이 여러번 나올 수 있기 떄문인데, 이는 같은 이동 횟수였을 때 중복 방문만 제거해주면 해결되는 부분이다.

따라서 visited 배열을 -1이면 방문하지 않은 상태, 그 이외에는 어느 이동 횟수 타이밍에 방문을 했는지를 저장하는 배열로 처리해서

visited 배열 안에 있는 정보가 만약 해당 이동 횟수와 같다면 큐에 넣지 않고 패스하고, 그렇지 않은 경우에는 큐에 넣고 visited 배열에 해당 이동 횟수 정보를 저장해주면 된다.

 

중간중간 앞 자리가 0인 것을 제거해주고, K번 이동을 마무리한 뒤 큐에 원소가 없는 경우에만 -1을 출력해주면 된다.

나머지의 경우는 그 중 최댓값을 출력해주면 되겠다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int visited[1000001];

int main(void)
{
    fastio;
    memset(visited, -1, sizeof(visited));
    int n, K;
    cin >> n >> K;

    queue<int> q;
    q.push(n);

    int move_num = 0;

    while (move_num < K && !q.empty())
    {
        int q_size = q.size();
        for (int i = 0; i < q_size; i++)
        {
            int cur = q.front();
            string cur_s = to_string(cur);

            q.pop();

            for (int j = 0; j < cur_s.size() - 1; j++)
            {
                for (int k = j + 1; k < cur_s.size(); k++)
                {
                    string next = cur_s;
                    swap(next[j], next[k]);
                    if (next[0] == '0')
                        continue;
                    if (visited[stoi(next)] != move_num)
                    {
                        q.push(stoi(next));
                        visited[stoi(next)] = move_num;
                    }
                }
            }
        }
        move_num++;
    }

    vector<int> result;

    while (!q.empty())
    {
        result.push_back(q.front());
        q.pop();
    }

    if (result.empty())
    {
        cout << -1 << "\n";
        return 0;
    }

    sort(result.begin(), result.end());

    cout << *(result.end() - 1) << "\n";
    return 0;
}