완전탐색(백트래킹) | S/W 문제해결 응용] 2일차 - 최대 상금

문제

SW Expert Academy

 

주어진 숫자판 중 2개를 선택해서 정해진 횟수만큼 서로의 자리를 교환할 수 있다.

교환이 끝나면 숫자판만큼의 상금을 얻는다. e.g) 4 3 2 5 1 => 43251원

정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 최대 금액 계산해라.

 

 

입력

• 첫 줄: 전체 테스트 케이스의 수
• 둘째 줄부터: 각 테이스 케이스가 한 줄씩 주어진다.
• 테스트 케이스는 숫자판이 띄어쓰기 없이 주어지고 교환 횟수도 주어진다.

3
123 1
2737 1
4852 3

 

 

출력

• #테스트케이스번호 최대 금액

#1 321
#2 7732
#3 88832

 

 

풀이

     

백트래킹
가능한 모든 조합을 고려해야 할 때 완전탐색이 사용된다.
그 중에서도 백트래킹은 트리를 탐색하는 방법으로 푸는 방법이다.

1. 문제를 탐색해야 하는 트리로 생각한다.

 

        시작 상태 [123]
              ↓ 

선택 1: [1, 2 교환] => [213]
           /       \
 [1, 2 교환]  [1, 3 교환] ....
         ↓          ↓
    리프1      리프2

2. 현재 상태를 정의한다.

현재의 상태와 현재까지 교환한 횟수를 확인한다.

3. 종료 조건을 정한다.

해당 문제의 경우 교환 횟수를 다 사용했을 때 멈춘다.

4. 가능한 모든 선택을 시도한다.

현재 상태에서 할 수 있는 모든 분기 시도.

예를 들어 [1, 3] [1, 2] [2, 3] 교환 모두 시도

5. 가능성 없는 경로는 탐색하지 않는다.

이미 같은 상태를 방문한 경우 제외

 

6. 조건 만족 값 갱신

현재 금액이 지금까지 나온 값 중 최대 금액인지 아닌지 확인하여 갱신

 

 

def dfs(nums, count):
    global max_value
	
    if count == chance:
    	#6
        max_value = max(max_value, int(''.join(nums)))
        return

    key = (''.join(nums), count)
    #5
    if key in visited:
        return
    visited.add(key)

    n = len(nums)
    #4
    for i in range(n):
        for j in range(i+1, n):
            nums[i], nums[j] = nums[j], nums[i]
            dfs(nums, count + 1)
            nums[i], nums[j] = nums[j], nums[i]  


T = int(input())
for t in range(1, T + 1):
    test_case, chance = input().split()
    nums = list(test_case)
    chance = int(chance)

    max_value = 0
    visited = set()
    dfs(nums, 0)
    print(f"#{t} {max_value}")