교환 (1039번) - 백준 (BOJ)

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

1039번: 교환

 

 

백준 - 교환 (1039번)

 

난이도 : Gold 3

알고리즘 : BFS (Breadth First Search) (너비 우선 탐색)

Time Complexity : O( K * (nC2)^2 )

 

if __name__ == '__main__':
    N, K = input().split()
    if len(N) == 1 or (len(N) == 2 and N[1] == '0'):
        print(-1)
        exit()
    K = int(K)
    q = [N]
    n = len(N)

    for _ in range(K):
        tmp = set()
        for s in q:
            cur = list(s)
            for i in range(n-1):
                for j in range(i+1, n):
                    if not i and cur[j] == '0':
                        continue
                    cur[i], cur[j] = cur[j], cur[i]
                    tmp.add(''.join(cur))
                    cur[i], cur[j] = cur[j], cur[i]
        q = tmp
    print(max(map(int, q)))

 

 

처음에 Greedy하게 정렬하는 방식으로 풀이하다가,

계속 "틀렸습니다"가 나와서 결국 질문 게시판을 찾아봤다.

역시 Greedy 정렬 방식에는 반례가 존재했다.

 

정렬을 다 해도 교환 횟수 K가 남는 경우에는 1, 2번째 자리수를 교환하도록 했는데,

최적의 정렬 경로가 아닌, 조금 돌아가면서 최댓값을 만드는 경우가 있었다.

그래서 "틀렸습니다"가 나올 수 밖에 없었다.

 

 

---

 

 

결국 BFS로 풀었고, 구현은 어렵지 않다.

 

각 교환 횟수마다 가능한 모든 경우의 수를 고려해서 교환하고,

그것을 다음 교환을 위한 후보군 queue에 넣는다.

 

여기서 중복 방지를 위해 queue를 set으로 설정했다.

그리고 0이 맨 앞으로 오는 경우도 제외해야 한다.

 

이렇게 모든 교환 횟수 K번이 지나고,

마지막에 남은 queue에서 최댓값을 찾으면 된다.

 

 

---

 

자릿수가 최대 7까지이고, K도 10 이하이기 때문에

너무 최적화에 힘쓸 필요는 없었다.

 

최적의 방법을 찾으려다가 괜히 시간만 오래걸렸다.

단순하게 풀기를 기억하자.