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

문제출처 : SW Expert Academy

문제

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

코드

# pass
import sys
sys.stdin = open('input.txt')

def bfs(cnt, ans):
    global min_ans, start
    # 첫 완성품일 경우
    if start == 0:
        if cnt == N:
            start = 1
            min_ans = ans

    # min_ans 정해진 이후의 경우
    else:
        # 빽트레킹/지금 과정결과가 min_ans보다 작으면 다음과정은 하지도말어~
        if min_ans <= ans:
            return

        else:
            if cnt == N:
                min_ans = ans
                return


    for i in range(N):
        if not visited[i]:
            visited[i] = 1
            new_ans = ans + arr[cnt][i]
            bfs(cnt+1, new_ans)
            visited[i] = 0


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N
    min_ans = 0
    start = 0

    bfs(0, 0)

    print("#{} {}".format(tc, min_ans))

장애물 1

문제

6/10 통과 - 시간초과

# 6/10 pass

def bfs(cnt, ans):
    global min_ans, start

    if cnt == N:
        if start == 0:
            start = 1
            min_ans = ans

        elif min_ans >= ans:
            min_ans = ans
        return

해결법

빽트레킹을 이용했어야 함!

   # 빽트레킹/지금 과정결과가 min_ans보다 작으면 다음과정은 하지도말어~
        if min_ans <= ans:
            return

        else:
            if cnt == N:
                min_ans = ans
                return