5일차 - 배열 최소 합

풀이 1 - 모든 순열 구해서 값 구하기 (거의 브루트 포스)

def perm(cnt):
    if cnt == n:
        vperm.append(sel.copy())
    else:
        for i in range(n):
            if check[i] == 0:
                sel[cnt] = varr[i]
                check[i] = 1
                perm(cnt + 1)
                check[i] = 0


for c in range(int(input())):
    n = int(input())
    number = [list(map(int, input().split())) for _ in range(n)]

    varr = [i for i in range(n)]
    vperm = list()

    sel = [0 for _ in range(n)]
    check = [0 for _ in range(n)]
    perm(0)

    vsum = list()
    for i in range(len(vperm)):
        varr = list()
        for j in range(n):
            varr.append(number[j][vperm[i][j]])
        vsum.append(sum(varr))

    print(f"#{c+1} {min(vsum)}")

 

런타임 에러가 나서 Fail(WA)이 떴는데 N이 3에서 10까지 일 때도 잘 되는걸 보면 아마 너무 많이 반복되는 재귀 함수 때문인 것 같은데.. 아무튼 그래서 백트래킹(가지치기; Pruning) 방법을 사용해서 풀었다..

 

풀이 2 - Pruning 수행한 백트래킹

def backtracking(cnt, v): # v : 현재 총값
    global vmin

    if v > vmin:
        return
    elif cnt == n:
        vmin = v
    else:
        for i in range(n):
            if visited[i] == 0:
                sel[cnt] = number[cnt][i]
                visited[i] = 1
                backtracking(cnt+1, v+sel[cnt])
                visited[i] = 0

for t in range(int(input())):
    n = int(input())
    number = [list(map(int, input().split())) for _ in range(n)]

    sel = [0 for _ in range(n)]
    visited = [0 for _ in range(n)]
    vmin = 1e12

    backtracking(0, 0)
    print(f"#{t+1} {vmin}")

 

backtracking 함수 조건문 중 else 이하를 보면 사실 거의 풀이 1에 사용했던 순열을 구하는 함수와 똑같다.

다른 점은 바로 if v > min : 과 elif cnt == n : 이다.

 

if문은 현재 총값이 지금까지 구했던 값 중 최솟값보다 클 경우 return으로 함수를 종료해서 가지치기(Pruning)을 해준 것이다. 이를 통해 유망성이 없는 경로를 차단해서 연산 횟수를 많이 줄일 수 있다!

 

그리고 elif문은 배열이 완성되었을 때 (sel 값이 다 찼을 때) 최솟값을 설정해준 것이다! 배열이 완성되었다는 뜻은 if문에서 걸리지지 않고 그대로 갔다는 뜻이니 최솟값이라는 뜻이 된다~ 따라서 vmin(최솟값)을 갱신해주면 된다~~!~!