백준 1039번 교환 (C++)

문제설명

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

1039번: 교환

 

문제 해결 

완전 탐색으로 풀었고, DFS, BFS 둘다 가능할 것 같은데 나는 BFS로 풀었다. 하나의 스텝 안에서 중복을 체크하기 위해 visit이라는 이름의 set 자료구조를 선언했다. 이 중복 체크를 DFS에서 하려면 재귀에 대해 잘 이해하고 코드를 짜야할 것 같다.

 

인덱스로 관리하기 위해 입력은 string 형태로 받았으며, while 문 안에서는 총 3번의 반복문이 이루어진다. 

1. 기존 q에 있었던 값들 (즉, 이전 스텝에서 q에 넣었던 수들)을 모두 탐색하기 위한 반복문

2. 꺼낸 수에 대해서, swap할 첫 인덱스에 대한 반복문

3. swap할 두번째 인덱스에 대한 반복문 

MAX값에 대해서는 마지막 step일 경우에 대해 탐색해주었다. 

당여하게도, 한번 꺼낸 값에 대해 swap했으면 다시 swap해서 제 숫자로 만들어야 한다. 

한번 로직을 떠올리면 구현 자체는 그리 까다롭지 않다. 하지만 나는 무진장 헤맸다. 

 

트러블슈팅

처음에는 그리디를 떠올렸다. 분명 문제를 풀기 시작할 때 완전탐색도 고려를 했었는데, 당시 생각했을 때는 그리디로 풀었을 때의 예외가 생각나지 않았고, 어떻게 완전탐색으로 풀어야 할 지도 잘 감이 안왔던 것 같다. 

 

초기 오류가 있는 로직은 다음과 같다. 현재 인덱스부터 마지막 인덱스까지 중 최댓값을 찾는다. 이때, 현재 인덱스가 최댓값이라면 다음 인덱스로 넘어간다. 그게 아니라면 최댓값과 현재 인덱스를 바꿔주고, 인덱스를 가리키는 값을 ++1 해준다. 이런 방식으로 해서 k번 탐색하기 전에 마지막 인덱스까지 갔다면, k에서 현재까지 swap한 횟수를 빼준다. 만약 짝수라면, 2번 swap해도 원본과 값이 똑같으니 넘어가고, 홀수라면 중복값을 탐색한다. 만약 중복값이 있다면 이 둘을 바꿔주면 되므로 무시하고, 중복값이 없는 경우에는 마지막 제일 작은 두 인덱스에 대해 swap을 진행한다. 

 

이런식으로 문제를 풀면 예제로 주어진 테스트케이스는 모두 통과한다. 그래서 문제 없이 잘 짰다고 생각했었다. 하지만 다음과 같은 예외에서 무너진다. 

421888 3

 

정답 : 888421

내 답 : 888124

 

그 이유는 최댓값을 찾을 때 마지막 인덱스부터 찾았기 때문이다. 물론 첫 인덱스부터 탐색하면 위 예제는 해결되지만, 또 다른 예제에서 무너진다. (e.g.124883 과 같은..) 구멍이 송송 난 로직이었던 것이다. 따라서 다음과 같은 결론이 나온다. 

 

그리디를 사용한 방법의 경우 공통된 최댓값이 있을 때가 예외가 된다.

바꾸는 과정에는 최댓값을 알 수 없으며, 해당 횟수만큼 뒤집어야 최댓값을 알 수 있다. 

 

이 문제를 통해 위 상황을 빨리 캐치하고 완전 탐색으로 푸는 게 중요하다는 것을 알게 되었다.

이 문제와 같이 수의 범위가 크지 않을 경우, 완전탐색일 거라고 짐작하고 이 방법부터 사용하는게 맞는 것 같다. 

 

코드 

#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

int main(void)
{
    string s;
    int k;
    int res = 0;
    cin >> s >> k;
    queue <string> q;
    q.push(s);
    int step = 0;
    while (!q.empty() && step < k)
    {
        set <string> visit; //한 단계 당 체크 
        int size = q.size();
        for (int ts = 0; ts < size; ts++)
        {
            string now = q.front();
            q.pop();
            for (int i = 0; i < now.length() - 1; i++)
             {
                for (int j = i + 1; j < now.length(); j++)
                 {
                    swap(now[i], now[j]); //바꿔보기
                    if (now[0] == '0')
                    {
                        swap(now[i], now[j]);
                         continue ; 
                    }
                    if (visit.find(now) == visit.end()) //없는 경우
                    {
                        if (step == (k - 1) && res < stoi(now))
                            res = stoi(now);
                        visit.insert(now);
                        q.push(now);
                     }
                    swap(now[i], now[j]); //원상복귀
                }
            }
        }
        step++;
    }
    if (res == 0)
        cout << "-1" << "\n";
    else
        cout << res << "\n";
    return (0);
}

 

참고

아이디어를 얻는 과정에 있어 다른 분의 코드를 참고하였기 때문에 링크를 남긴다. 

https://yabmoons.tistory.com/152

[ 백준 1039 ] 교환 (C++)