[SWEA D3] 5209. [파이썬 S/W 문제해결 구현] 5일차 - 최소 생산 비용 Python

문제출처> 5209. [파이썬 S/W 문제해결 구현] 5일차 - 최소 생산 비용

🚩 문제설명

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

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

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

이때 1-C, 2-A, 3-B로 제품별 생산 공장을 정하면 생산 비용이 21+11+31=63으로 최소가 된다.

[입력]

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

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

[출력]

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

---

입력

3
3
73 21 21
11 59 40
24 31 83
5
93 4 65 31 66
63 12 60 60 84
87 57 44 35 20
12 9 40 12 40
60 21 3 49 54
6
55 83 32 79 53 70
77 88 80 93 42 29
54 26 5 10 25 94
77 92 82 83 11 51
84 11 21 62 45 58
37 88 13 34 41 4

출력

#1 63
#2 78
#3 129

---

📝 문제풀이

---

def dfs(product):
    global total, Sum

    if product == N:
        if total > Sum:
            total = Sum
        return

    if total <= Sum:
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            Sum += lst[product][i]
            dfs(product + 1)
            visited[i] = 0
            Sum -= lst[product][i]


T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    lst = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N
    Sum = 0
    total = 987654321

    dfs(0)
    print(f'#{test_case} {total}')

---

🔧 해결방안

1. 상품을 어느 공장에서 생산했느냐에 따라서 체크하며 상품1, 상품2, 상품3.. 단계별로 dfs 재귀호출을 진행한다.
   product가 최종적으로 N인 마지막줄까지 다 따지게 되면 가장 최소 비용변수인 total이 지금 합계보다 큰지 확인한다.
   맞으면 total을 Sum으로 갱신하여 가장 최소 값을 넣도록 한다.
   
   
2. 재귀호출을 하여 상품비용을 하나씩 더하고 있는 값 Sum이 total보다 크거나 같으면 더 이상 유망하지 않아 재귀호출하는 것이 의미가 없음으로 return하여 백트래킹한다.
   if total <= Sum: return
   
   
3. for문을 돌리면서 어디 공장을 방문했는지 visited변수로 체크해주고 아직 방문한 공장이 아니라면 선택한 상품에 해당하는 공장 생산 비용을 Sum에 더해나간다.
   dfs(product+1)을 하면서 다음 상품을 찾아나간다. 재귀호출이 종료되면 다시 방문visited[i]=0, Sum -=[product][i]를 하여 다시 재귀호출 하기전 원 위치로 돌이킨다.