[백준] 1039 교환 (Python)

문제

백준 1039 교환 문제를 풀었습니다.

너무 어렵게 생각할 문제가 아니었던 것 같습니다.

• 힌트 1 : BFS 맞긴 합니다.
• 힌트 2 : 완전탐색과 다를 바 없음.
• 힌트 3 : 시간 초과날 것 같은데..? 하시겠지만 안납니다. BFS로 순회하며 완전탐색하시면 됩니다.

풀이

BFS로 K번의 연산을 완전탐색해줍니다.

연산 구현은 다음과 같습니다.

16375인 경우에의 K=1 연산

시작 큐 : 16375

while q, q에서 16375를 꺼내서 연산 시작.

1. ‘1’을 6, 3, 7, 5와 바꾼다. 그 결과를 큐에 넣는다.
   • Q : 61375 36175 76315 56371
2. ‘6’을 3,7,5와 바꾼다. 그 결과를 큐에 넣는다.
   • Q : 61375 36175 76315 56371 13675 17365 15376
3. ‘3’을 7,5와 바꾼다. 그 결과를 큐에 넣는다.
   • Q : 61375 36175 76315 56371 13675 17365 15376 16735 16573
4. ‘7’을 5와 바꾼다. 그 결과를 큐에 넣는다.
   • Q : 61375 36175 76315 56371 13675 17365 15376 16735 16573 16357

단, Q에 들어가는 값이 0으로 시작하지 않고 이미 큐에 있지 않은 경우에만 넣어줍니다. (가령 1111 이면 무의미하게 같은 값만 많이 들어가겠죠? 굳이 넣을 필요 없으니 안넣겠습니다.)

그런데 이제 몇 번 연산을 했는지를 꼭 세어줘야합니다. 그래서 Q에는 결과숫자값과, 연산횟수(tempK)를 함께 tuple로 묶어서 넣어주었습니다. (내부에 있는 값이 바뀌지 않을 것이며, 바뀌어서도 안되기 때문에 튜플로 넣어주었습니다. 휴먼 에러로 어디선가 값이 바뀌고 있다면 컴파일 에러를 내도록요.)

그래서, K번 연산이 끝났다면, K+1번째 연산을 시작하기 직전에 while 문에서 탈출해줍니다.

• 정확히는 그냥 가장 큰 값을 찾아서 return 해주시면 됩니다. 왜냐하면 정상적으로 while문에서 탈출되었다면, 즉 q가 텅 비는 사태가 발생한다면 이는 K번까지 연산을 못하고 “다음에 계산할 수를 못찾은” 경우이기 때문입니다. (-1을 뱉어야 하는 예외 사항들이 이런 케이스에 해당합니다. 예외 사항으로 고려해주셔야하는 케이스는 하단에 적겠습니다.)
• 왜 하필 K+1번째 연산을 시작하기 직전일까요? 큐에 남아있을 노드들을 생각해보면 쉽습니다. 2번째 연산이 시작되는 시점은, 1번째 연산을 통해 얻을 수 있는 모든 결과값들을 전부 얻어서 큐에 넣었을 때입니다. 우리는 K번째 연산에서 나온 모든 값에서 최대값을 구해야 하므로, K+1번째 연산이 시작하기 전, 즉 튜플로 BFS 노드에 함께 묶여져있던 ‘연산 횟수’가 K가 되는 순간에 return해주면 됩니다.

예외처리를 고려하셔야 하는 케이스는 다음과 같습니다.

1. 0, 1, 2, 3, …, 9 등 한자리 수
2. 0으로 끝나는 두자리 수 (0이 앞으로 가면 안되기 때문입니다.)

• 0으로 끝나는 n자리 수(n>=3)은요? : 예외가 아닙니다. 100인 경우에는 0과 0이 자리를 바꾸어 100이라는 값을 만들 수 있습니다.

while loop에서 적절하게 탈출하고 있다면 별도의 예외를 작성하지 않아도 정상적으로 동작합니다.

답

from collections import deque 

def bfs(start, K) :
  startK = 0
  q = deque([(start, startK)])
  while q :
    if (q[0])[1] == K :
      return max(x[0] for x in q)
    tempStart, tempK = q.popleft()
    for i in range(0,len(start)-1) :
      for j in range(i+1, len(start)) :
        tempN = list(tempStart)
        tempN[j], tempN[i] = tempN[i], tempN[j]
        tempN = ''.join(tempN)
        if tempN[0] != '0' and (tempN,tempK+1) not in q :
          q.append((tempN,tempK+1))
  
  return -1

def _1039() :
  N, K = map(int, input().split())
  print(bfs(str(N), K))

_1039()