[SWEA|파이썬] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (D3)

문제

https://tinyurl.com/2mdtddm2

SW Expert Academy

 

 

🐍파이썬

def dfs(cnt):
    global answer
    if cnt == t:	#최대 교환횟수에 도달하면
        temp = ''.join(num)	#문자열 변환
        answer = max(answer, temp)	#answer와 비교해 더 큰 숫자를 answer변수에 담기(문자열 타입의 숫자도 대소비교 가능)
        return	#종료
    for i in range(len(num)):
        for j in range(i+1, len(num)):
        	#하나씩 교환
            num[i], num[j] = num[j], num[i]
            temp = ''.join(num)
            #get(): visited에 (temp, cnt)라는 key가 존재하지 않으면 1리턴
            #방문한 적 있다면 재방문 금지->시간초과 방지
            #방문한 적 없다면 방문처리 후 방문
            if visited.get((temp, cnt), 1):
                visited[(temp, cnt)] = 0
                dfs(cnt+1)
            #dfs수행이 종료되었다면 다른 경로의 dfs 수행을 위해 num 원상복구
            num[i], num[j] = num[j], num[i]	
            
T = int(input())
for test_case in range(1, T + 1):
    num, t = input().split()
    num = list(num)
    t = int(t)	#교환횟수
    answer = "0"	#answer 초기화
    visited = {}	#방문했는지 확인하는 용도
    dfs(0)
    print("#{} {}".format(test_case, answer))