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

이번 문제는 N종의 제품을 N곳의 공장에서 한 곳당 한 가지씩 생산할 때, 최소 생산 비용이 얼마인지 구하는 문제이다.

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    answer = float('inf')
    visited = [False for _ in range(N)]

    def factory(product, fee):  # product: 현재 제품, fee: 생산 비용
        global answer
        if fee >= answer:       # 가지치기
            return
        if product >= N:        # 제품:공장 = 1:1 배정 완료
            if answer > fee:
                answer = fee
                return
        
        for j in range(N): 
            if not visited[j]:
                visited[j] = True
                factory(product+1, fee+arr[product][j])
                visited[j] = False

    factory(0, 0)
    print(f"#{test_case} {answer}")

오랜만에 혼자 힘으로 끝까지 다 푼 문제였다. 조금씩 연습하는 게 효과를 보이는걸까!!

항상 함수를 작성할 때, 이건 dfs일지 bfs일지 고민을 했었다. 그러다보니 함수명을 정하는 부분에서부터 막혀서 그 뒤의 진행을 생각하려고만 하면 머리가 복잡해졌었지. 그래서 아예 dfs랑 bfs에 대해 생각하지 않고, 직관적인 함수명을 정해서 어떻게 구현할지에 대해서만 집중했다.

처음 오류가 났던 부분은 for j in range(N): 부분이었다. 처음에 각 공장별 생산 비용을 저장한 리스트가 2차원 리스트니까 당연히 이중 for문을 썼었는데, 테스트케이스를 돌렸을 때의 결과가 이상하게 나와서 다시 살펴본 부분이다.

for i in range(N)를 빼고 factory() 재귀 부분에서 바로 다음 제품에 대해서 생산 비용을 선택하러 넘어갈 수 있도록 해줬다. 그냥 말로 풀려니까 잘 설명이 안 되는군...

5209.최소 생산 비용_풀이