SWEA 5209 최소 생산 비용 (파이썬)

https://swexpertacademy.com/main/talk/solvingTalk/boardCommuView.do?commuId=AWrmdCqqQeYDFARG 

SW Expert Academy

 

---

풀이 및 해설(주석)

def solve(depth, sums):
    global rst
    # depth가 N이 되면 return
    if depth == N:
        rst = min(rst, sums)
        return
    # 가지치기
    if sums >= rst:
        return
    # visit체크 확인 하고 안갔으면 ㄱㄱ
    # 같은 행과 열을 가지지않음
    for i in range(N):
        if visit[i]:
            continue
        visit[i] = 1
        solve(depth+1, sums+fac[depth][i])
        visit[i] = 0

for tc in range(int(input())):
    N = int(input())
    fac = [list(map(int, input().split())) for _ in range(N)]

    rst = 1e9
    visit = [0] * (N)
    solve(0, 0)
    print(f'#{tc+1}', rst)