백준 1039 교환

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

처음 이 문제를 보고 몇일전에 풀었던
https://www.acmicpc.net/problem/1083
이 문제가 떠올랐다. 이 문제에서는 최대 k번 스왑이 가능했기 때문에 k번 안에 가장 큰 경우의 수가 나온다면 문제가 해결되었다. 그렇기 때문에 그리디 방식과 버블정렬의 개념을 이용해 문제를 풀었었다.

하지만 1039 교환 문제는 최대 K번이 아니라 K번을 반드시 교환해주어야 한다.
처음에는 이 문제도 그리디로 풀릴것 같아서 그리디로 접근을 해보았지만 잘 안되었다.

위의 문제와 마찬가지로 제일 뒤에서 부터 큰 수를 찾아 정렬된 위치에 옮겨넣는 방식으로 진행했었는데, 이 경우 65499를 교환한다고 생각해보면,
내 로직에 따르면 65499 -> 95496 -> 99456이 나왔고, 정답은 99456이었다.
결국 완전탐색을 통해 찾아야 했다.
완전탐색으로 모든 경우를 스왑해 찾는다고 생각해보면, 최대 7자리 자리수중에서 2개를 고른뒤(7C2) 높이 k만큼 탐색해야 하기 때문에 35^k만큼 나오는데 이 방법은 시간초과가 나온다.

bfs든 dfs든 탐색을 하면서 반복을 제거해줘야만 했다.
dfs방식과 bfs방식 두가지 풀이가 있는데,
dfs방식에선 재귀와 dp를 이용해 연산을 줄였고,
bfs에선 큐에서 방문배열을 이용해 중복을 제거하였다.

#1 dfs 풀이

n,k = map(int,input().split())
nlist = list(str(n))
length = len(nlist)
dp = [[-1]*11 for i in range(1000010)]
def dfs(node,depth):
    if depth == k:
        return int(node)
    if dp[int(node)][depth] != -1:
        return dp[int(node)][depth]
    for i in range(length-1):
        for j in range(i+1,length):
            tolist = list(node)
            if i == 0 and tolist[j] == '0':
                continue
            tolist[i], tolist[j] = tolist[j], tolist[i]
            tostr = ''.join(tolist)
            dp[int(node)][depth] = max(dp[int(node)][depth], dfs(tostr,depth+1))
    return dp[int(node)][depth]

print(dfs(str(n),0))

#2 bfs 풀이

from collections import deque
n,k = map(int,input().split())
length = len(list(str(n)))
queue = deque([])
queue.append((str(n),0))
ans = 0
while queue:
    visited = {}
    for _ in range(len(queue)):
        x,cnt = queue.popleft()
        if cnt == k:
            ans = max(ans,int(x))
            continue
        for i in range(length-1):
            for j in range(i+1,length):
                tolist = list(x)
                if i == 0 and tolist[j] == '0':
                    continue
                tolist[i],tolist[j] = tolist[j],tolist[i]
                tostr = ''.join(tolist)
                if tostr not in visited:
                    visited[tostr] = 1
                    queue.append((tostr, cnt+1))

if n < 10 or (length == 2 and n%10 == 0):
    print(-1)
else:
    print(ans)