[Python] SWEA 5209: 최소 생산 비용

https://swexpertacademy.com/main/talk/solvingClub/problemSubmitHistory.do?contestProbId=AYN4GqCaLJwDFASV&solveclubId=AYYF1QaaEvoDFAVw&problemBoxTitle=230329+%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5&problemBoxCnt=9&probBoxId=AYcrBr-KQhQDFAVa 

접근 로직
단순하게 순열로 접근해서 모든 경우의 수를 구한 후(Brute-force) 백 트래킹으로 시간을 줄여주려 했다. 순열과 백트래킹 연습하기 적절한 문제

첫 번째 접근(Brute-Force)

def min_money(lst):
    minV = 0
    global tmp #tmp에 가장 작은 값 저장할 것
    for i in lst:
        minV += arr[lst[i]][i] #나는 보통 백 트래킹을 걸 때 여기서만 건다. 변수를 하나만 받아서 처리하기 가능한게 이 순간 뿐,,,
        if minV > tmp:
            return
    if tmp > minV:
        tmp = minV
    return tmp

def per(k):
    if k==N:
        min_money(result)
    for i in range(N):
        if not used[i]:
            result[k] = idxlst[i]
            used[i] = True
            per(k+1)
            used[i] = False

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    idxlst = [idx for idx in range(N)]
    result = [-1] * N
    used = [False] * N
    tmp = 999999999999999999999
    per(0)
    print(f'#{tc} {tmp}')

모든 순열을 만든 후, 그 순열에서 만들 수 있는 값을 모두 구한 후 최소값을 뽑아내는 것을 목적으로 했다. 값은 잘 나오니 제한 조건을 걸어주어 백 트래킹을 하려고 했다.

 

ANS(Brute-Force, 백 트래킹)

def per(k, curS):
    global tmp
    if curS > tmp:
        return
    if k==N:
        if curS < tmp:
            tmp = curS
    for i in range(N):
        if not used[i]:
            used[i] = True
            per(k+1, curS+arr[i][k])
            used[i] = False

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    used = [False] * N
    tmp = 999999999999999999999
    per(0, 0)
    print(f'#{tc} {tmp}')

맨 처음에는 idxlist를 이용해서 하나하나 순열을 구하려고 했는데, 생각해보니 그 과정이 매우 불필요했다. 또한 함수를 하나로 줄여 호출에 필요한 시간을 줄여 주려 했으며, 변수를 두 개 받아 실시간으로 변수 추적이 가능하도록 해 백 트래킹을 가능하도록 했다. 백 트래킹은 값을 실시간으로 볼 수 있어야(특정 조건을 넘으면 아예 특정 단계가 시행되지 않도록 해야 한다.) 하므로 백 트래킹을 추적할 수 있어야 한다. 백트래킹 연습 많이 하자! 순열을 다 만든 후 잘라내는게 아니라, 순열을 만드는 과정 중에서도 최소값 이상이 되면 냅다 그만둬야 함.