[SWEA] 5209_최소 생산 비용 (백트랙킹 이용)

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. dfs의 n은 현재 행이고, items는 현재까지 생산한 제품의 열이 담길 리스트이고, total은 현재까지의 비용이 담긴다.

2. 한 행씩 내려가면서 각 행에서 생산할 제품을 고른다.

3. 모든 열을 돌면서 만약 그 열이 지금까지 생산한 제품의 열이 아니라면 items에 열을 넣고 재귀를 실행한다.

실행한 이후에는 다시 items에서 넣었던 열을 빼줘야 한다.

4. 만약 진행하다가 현재까지의 비용이 ans를 넘으면 return한다. (가지치기)

5. n이 N이 된다면 모든 공장이 제품을 선택한것이기 때문에 그때의 total과 ans를 비교해서 더 작은 값을 ans에 넣는다.

def dfs(n, items, total):
    global ans

    if total >= ans:
        return
    if n == N:
        ans = min(ans, total)
        return

    for i in range(N):
        if i not in items:
            items.append(i)
            dfs(n+1, items, total+matrix[n][i])
            items.pop()


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    ans = 1500
    dfs(0, [], 0)
    print('#{} {}'.format(tc, ans))