1244. [S/W 문제해결 응용] 2일차 - 최대 상금

백트래킹 문제이다. 

 

조건은 

1. 교환 횟수를 다 쓰거나

2. 이미 방문했던 노드이면 더이상 탐색하지 않는다. 

 

def dfs(cnt):
    global answer
    if cnt == c:
        answer = max(answer, int(''.join(map(str, lst))))
        return
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            lst[i], lst[j] = lst[j], lst[i]
            
            check = ''.join(lst)
            if (cnt, check) not in track:
                dfs(cnt + 1)
                track.append((cnt, check))
    
            lst[j], lst[i] = lst[i], lst[j]


T = int(input())
for test_case in range(1, T + 1):
    num, count = list(map(str, input().split()))
    c = int(count)
    lst = [x for x in num]
    track = []
    answer = 0
    dfs(0)
    print(f'#{test_case} {answer}')

 

백트래킹 사용시 주의해야할 점

• return 까먹지 말고 써주기
• global 변수 명시해 주기
• 조건에 따라 가지치기

 

코테 문제 풀 때 주의할 점

• 배열인지 아닌지 처리 잘하기 - map 
• 타입 주의하기
• python 출력 시 f'{변수명} {변수명}' 사용하기