[백준] 1039 교환 (골드 3)

from collections import deque
import sys
input = sys.stdin.readline


N, K = map(int, input().rstrip().split())
size = len(str(N))

queue = deque()
queue.append((str(N), 0))
visited = set()


answer = 0

while queue:

    now, cnt = queue.popleft()

    ## K번이 지났다면 최댓값 갱신해준다.
    if cnt == K:
        answer = max(answer, int(now))
        continue

    for i in range(size - 1):
        for j in range(i+1, size):

            ## 교환 불가한 상황은 무시하기
            if i == 0 and now[j] == "0":
                continue

            now = list(now)
            now[i], now[j] = now[j], now[i]
            
            ## 방문하지 않은 배치라면 cnt를 1 증가시킨 후 queue에 넣어준다.
            if ("".join(now), cnt + 1) not in visited:
                queue.append(("".join(now), cnt+1))
                visited.add(("".join(now), cnt+1))

            
            now[i], now[j] = now[j], now[i]

print(answer if answer > 0 else -1)

 

처음에 그리디로 접근했는데 시간초과가 났다.

 

for문으로 기준 수를 정하고, 그 수 오른쪽의 수 중 가장 큰 수와 교체하는 아이디어였다. (왜 시간초과가 뜨는 지 잘 모르겠음.)

 

그래서 bfs 방식으로 돌렸더니 AC를 받았다