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

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

SW Expert Academy

이 문제는 copy모듈의 deepcopy와 itertools모듈의 combinations모듈을 사용하였다. 

깊이 우선 탐색(dfs)을 사용하여 풀었는데, 교체 횟수가 짝수번 남으면 visit에 넣었고, visit 중에 가장 큰 값을 답으로 하였다. 짝수번 남은 것만을 넣은 이유는 짝수번을 넣었을 경우, 같은 교체를 2회 반복하면 다시 자기 자신으로 돌아올 수 있기 때문에, 가능한 경우의 수만 visit에 넣도록 하였다. 해결한 코드는 다음과 같습니다.

from itertools import combinations
from copy import deepcopy


def chanum(numbers, comb):
    global visit
    sub = 0
    num2=deepcopy(numbers)
    temp = num2[comb[0]]
    num2[comb[0]] = num2[comb[1]]
    num2[comb[1]] = temp
    return num2


def cal(numbers):
    sub=''
    for i in numbers:
        sub=sub+str(i)
    return sub




def solution(numbers, change, comb):
    global answer
    global visit
    stack = []
    stack.append([numbers, change, 0])
    visit.append(cal(numbers))
    while stack:
        numbers, change, count = stack.pop()
        for i in comb:
            newnums=chanum(numbers,i)
            sub=cal(newnums)
            if sub not in visit and count<change:
                stack.append([newnums,change,count+1])
                if (change-count-1)%2==0:
                    visit.append(sub)
    return max(visit)

t = int(input())
for test in range(1, t + 1):
    number, change = input().split()
    change=int(change)
    numbers = []
    visit=[]
    for i in number:
        numbers.append(int(i))
    comb = list(combinations(range(len(numbers)), 2))
    answer=solution(numbers,change,comb)
    print('#{} {}'.format(test,answer))