[SWEA] 5209. 최소 생산 비용

# 문제 설명

 

# 입출력 예시

입력	출력
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

 

# 코드 풀이.  1차 시도- sorted by asc

from itertools import permutations # 시간초과(4/10)- 2초이내

for tc in range(int(input())):
    n = int(input())
    p = [list(map(int, input().split(' '))) for _ in range(n)] # 제품*공장
    mini = 9999 # 최소 생산비용

    def sorted_asc(i, visited): # 제품i의 최적의 공장
        for y, j in sorted([(y, j) for j, y in enumerate(p[i])]):
            if not visited[j]:
                return j, y
    
    order = list(permutations(range(n))) # 제품들의 방문 순서
    for oi in range(len(order)):
        visited = [False]*n # 공장이 선택됬는지
        cost = 0
        for j in order[oi]:
            k, c = sorted_asc(j, visited) # i제품의 공장 선택
            visited[k] = True # 해당 공장 방문
            cost += c
        if cost < mini:
            mini = cost
    print(f"#{tc+1} {mini}")

 

# 코드 풀이 2.  2차 시도- Brute force

# 시간초과(5/10)
for tc in range(int(input())):
    n = int(input())
    product = [list(map(int, input().split(' '))) for _ in range(n)] # 제품*공장
    min_cost = 999 # 최소 생산비용

    def dfs(i, path):
        global min_cost
        if i == n:
            sum_path = sum([product[i][j] for i,j in enumerate(path)])
            min_cost = min(sum_path, min_cost)
            return
        for j, x in enumerate(product[i]):
            if j not in path:
                dfs(i+1, path + [j])
    
    dfs(0, [])
    print(f"#{tc+1} {min_cost}")

 

# 답안 코드

def dfs(i, sum):
    global min_cost
    if i == n:
        if sum < min_cost:
            min_cost = sum
        return
    elif sum > min_cost:
        return
        
    for j in range(n):
        if not visited[j]:
            visited[j] = True
            dfs(i+1, sum + product[i][j])
            visited[j] = False

for tc in range(int(input())):  
    n = int(input())
    product = [list(map(int, input().split(' '))) for _ in range(n)] # 제품*공장
    visited = [0]*n
    min_cost = 999 # 최소 생산비용
    
    dfs(0, 0)
    print(f"#{tc+1} {min_cost}")

 

# 핵심 포인트

• sum의 값이 최소비용보다 크면, 정답일 가망이 없는 것이므로 return 한다.
• testcase 에서 자주 사용하는 코드는 for문 바깥에 빼두어야 다시 정의를 안한다.
• visited 로 해당 공장이 방문했는지 여부를 bool 값으로 저장한다.