Stack2 - 배열 최소합

백트래킹을 활용하여 해결한다.

최소합(=최종 답변)을 저장할 변수(minn)와 계산되는 값(=최솟값과 비교할 값)을 저장할 변수(res), 방문한 열을 체크할 리스트(chk)를 사용한다.

def calc(num):
    global res,minn
    
    if minn<res: #가망없음
        return
    
    if num==N: #모든 리스트를 돌았다
        if minn>res:
            minn=res
        return 
    
    for i in range(N):
        if chk[i]==1:
            continue
        chk[i]=1
        res+=arr[num][i]
        calc(num+1)##
        chk[i]=0
        res-=arr[num][i]


for tc in range(1,int(input())+1):
    N= int(input())
    arr= [list(map(int, input().split())) for _ in range(N)]
    chk=[0]*N
    res=0
    minn=123456
    
    calc(0)
    print(f'#{tc} {minn}')

텍스트