배열 최소 합 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4880

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIc7KqfQDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

NxN 배열에 숫자가 들어있다. 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 하려고 한다. 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다. 조건에 맞게 숫자를 골랐을 때의 최소 합을 출력하는 프로그램을 만드시오.   예를 들어 다음과 같이 배열이 주어진다. 이경우 1, 5, 2를 고르면 합이 8로 최소가 된다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50   다음 줄부터 테스트 케이스의 첫 줄에 숫자 N이 주어지고, 이후 N개씩 N줄에 걸쳐 10보다 작은 자연수가 주어진다. 3≤N≤10

출력

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

예시

입력	출력
3 3 2 1 2 5 8 5 7 2 2 3 9 4 7 8 6 5 5 3 7 5 5 2 1 1 9 3 3 8 3 1 9 2 8 8 6 1 5 7 8 3 5 5 4 6 8	#1 8 #2 14 #3 9

---

2. 문제풀이

파이썬 스택 2일차 연습문제 중 하나인 배열 최소 합 문제이다. 말이 저렇지 사실 조합문제이다. N X N 행렬일때 0~N까지 조합을 만들어서 제일 작은값을 찾으면 된다. 조합 문제는 DFS를 구현하면 쉽게 만들 수 있다. 계산량을 줄이기위해 가지치기를 이용하면 연산량을 줄일 수 있다.

 

---

3. 소스코드

#4881 D2 배열 최소 합
 
def dfs(idx, _sum):
    global min_result
    if idx == N:
        if _sum < min_result:
            min_result = _sum
        return
    #가지치기
    if _sum >= min_result:
        return
    for i in range(N):
        #갔던 세로줄은 사용불가하게 바꾸기
        if use_check[i]:
            use_check[i] = False
            dfs(idx+1, _sum + map_list[idx][i])
            use_check[i] = True
 
T = int(input())
for t in range(1, T+1):
    N = int(input())
    map_list = [list(map(int, input().split())) for _ in range(N)]
    use_check = [True for _ in range(N)]
    min_result = 987654321
    dfs(0, 0)
    print("#{} {}".format(t, min_result))