[bfs/백준] 1039번 : 교환

- 문제 : https://www.acmicpc.net/problem/1039

 

문제 이해 

- 주어진 수의 i번째 자리수와 j번째 자리수를 k번 바꿔서 타겟 숫자가 될 수 있는지 출력하는 문제다.

- 문제가 그리디 같기도, 브루트포스? 같기도 해서 bfs로 어떻게 풀지 몰랐던 문제다. 

- 주의해야할 점은 두 가지가 있는데, 다음과 같다.

  1. 연산을 한 번 해서 이전과 같은 숫자가 나와도 다른 케이스로 쳐줘야 한다. 그래서 visit를 set으로 구현해서 원소들의 중복을 없애야 한다.

  2. 숫자를 바꿨을 때 가장 앞에 있는 수가 0이면 세지 않는다.  

- 그리고 i, j번째 수를 일일히 바꾸면 시간이 오래 걸리지 않을까 싶었는데 이중 for문으로 i, j를 바꾸면서 진행해야 했다. 

 

풀이 로직

- 입력값을 입력 받은 뒤 visit와 queue를 초기화 한다. 

  visit는 (진행하는 숫자, 연산횟수)를 원소로 가진 set

  queue는 [진행하는 숫자, 연산횟수]를 원소로 가진 배열

- while문으로 bfs를 진행하면서 연산횟수가 k와 같다면 정답 후보이다. 이때 answer = max(answer, 연산횟수)를 통해 가능한 최대값을 계속 업데이트한다.

- 연산횟수가 k가 아니라면 숫자를 배열로 변경한 뒤 이중 for문으로 i번째 수와 j번째 숫자를 바꾼다.

- 바꾼 숫자를 다시 ''.join()으로 하나의 숫자를 만들고 해당 숫자를 이전에 visit 하지 않았다면, visit 처리한 뒤 queue에 추가한다.

- 다른 숫자들도 숫자를 바꿔야 하므로 위에서 바꿨던 숫자를 다시 원상복구한다.

- while문에서 answer의 값이 0이 아니라면 정답이 있으므로 answer를 출력하고, 여전히 0이라면 -1을 출력한다.

 

정답 풀이 

n, k = map(int, input().split())
m = len(str(n))

visit = set()
visit.add((n, 0)) # 숫자, 연산횟수
queue = [[n, 0]]
answer = 0

while queue:
    number, times = queue.pop(0)
    
    if times == k:
        answer = max(answer, number) # 최대 숫자 업데이트
        continue
        
    number = list(str(number))
    for i in range(m - 1):
        for j in range(i + 1, m):
            if i == 0 and number[j] == '0':
                continue
            
            number[i], number[j] = number[j], number[i]
            temp = int(''.join(number))
            if (temp, times + 1) not in visit:
                queue.append([temp, times + 1])
                visit.add((temp, times + 1))
            # 배열 원상복구
            number[i], number[j] = number[j], number[i]
                
if answer == 0:
    print(-1)
else:
    print(answer)

 

 

참고한 블로그 : 백준-1039번-교환-파이썬