[Algorithm] Baekjoon 1039번 : 교환

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

1039번: 교환

 
int n, k;
int answer = -1;
bool visited[1000001] = { false };
 
struct Node
{
    int num;
    int count;
};
 
void BFS()
{
    queue<Node> q;
    q.push({ n,0 });
 
    if (n < 10)
    {
        cout << -1;
        return;
    }
 
    while (!q.empty())
    {
        int curNum = q.front().num;
        int curCount = q.front().count;
        q.pop();
 
        if (curCount == k) continue;
 
        string s = to_string(curNum);
 
        for (int i = 0; i < s.size(); ++i)
        {
            for (int j = i + 1; j < s.size(); ++j)
            {
                if (i == 0 && s[j] == '0') continue;
 
                string ts = s;
 
                char temp = ts[i];
                ts[i] = ts[j];
                ts[j] = temp;
 
                int tNum = stoi(ts);
 
                if ((k - curCount + 1) % 2 == 0)
                {
                    answer = max(answer, tNum);
                }
 
                if (visited[tNum]) continue;
                visited[tNum] = true;
                q.push({ tNum,curCount + 1 });
            }
        }
    }
 
    cout << answer;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    BFS();
}
 

 

k번의 숫자교환을 통해 얻을 수 있는 최대값을 구하는 문제이다.

완전한탐색을 시도하겠지만, 문제의 조건에 맨 앞 숫자가 0이되는 경우는 안된다고 했으니 해당 예외처리를 꼭 해줘야 한다. 

그렇기 때문에 '첫번째 수'와 '이외의 다른 수'의 교환을 시도할 때, '이외의 다른 수'는 절대 0이면 안된다.

 

그리고 이 문제에서 주의해야할 점은 반드시 k번의 교환을 마친 후에 얻은 수의 최대값을 구한다는 것이다.

교환하는 도중에 얻은 값을 무작정 업데이트하면 안된다.

다만, 교환한다음에 남은 교환의 수가 짝수라면 해당 수는 업데이트 해도된다.

왜? 바꾼것을 똑같이 바꾸면 어차피 결국 해당숫자는 k번의 교환을 끝낸다음 만들 수 있는 숫자이기 때문이다.

 

그다음은 방문체크를 통해서 해당노드를 큐에 넣을지 말지 정하면된다.

 

여기서 내가 한가지 찝찝한 것은, 47번째 if문과 52~54(방문체크)의 코드의 순서를 바꾸면 왜 안되냐는 것이다..

1%가 보이기도 전에 틀렸다고 뜨는데, 사실 왜그러는지를 모르겠다..