[SWEA 5209번] 최소생산비용 - 파이썬(python)

SW Expert Academy

분류

• DFS
• 백트래킹

문제

A사는 여러 곳에 공장을 갖고 있다. 봄부터 새로 생산되는 N종의 제품을 N곳의 공장에서 한 곳당 한가지씩 생산하려고 한다.

각 제품의 공장별 생산비용이 주어질 때 전체 제품의 최소 생산 비용을 계산하는 프로그램을 만드시오.

예를 들어 3개의 제품을 생산하려는 경우 각 공장별 생산비용은 다음과 같이 주어진다.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 제품 수 N이 주어지고, 이후 제품당 한 줄 씩 N개의 줄에 걸쳐 공장별 생산비용 Vij가 주어진다. 3<=N<=15, 1<=Vij<=99

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이

• 한 줄에서 하나만 선택할 수 있고 선택한 인덱스는 다음줄에서 선택할 수 없기 때문에 방문배열을 체크하면서 풀이해야 한다.
• 모든 경우의 수를 탐색할 경우 시간초과가 발생하기 때문에 백트래킹을 통해 가지치기를 해줘야 한다.

코드

def dfs(level, summ):
    global mn
    if mn<summ:
        return
    if level == N:
        if mn > summ:
            mn = summ
            return
    for i in range(N):
        if visited[i] == 1: continue
        visited[i] = 1
        dfs(level + 1, summ + factory[level][i])
        visited[i] = 0

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    factory = [list(map(int, input().split())) for _ in range(N)]
    visited=[0]*N
    mn=21e8

    dfs(0,0)
    print(f'#{test_case} {mn}')