문제 출처 : [SWEA] 4881 배열 최소 합
learn -> course -> programming intermediate -> stack2 -> 배열 최소 합

문제

NxN 배열에 숫자가 들어있다. 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 하려고 한다. 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다.

조건에 맞게 숫자를 골랐을 때의 최소 합을 출력하는 프로그램을 만드시오.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다. 1≤T≤50

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

출력

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

코드

# 최소합을 찾는 함수
def find_sum(num):
    # 최종 결과를 저장할 변수와, 숫자들의 합을 임시로 저장할 변수
    global min_sum, sum_num

    # 찾은 최소합보다 임시로 저장한 합이 더 클 경우엔 더 이상 최소값이 아니기 때문에 return
    if min_sum < sum_num:
        return

    # 마지막줄까지 탐색을 끝낸 경우
    if num == N:
        if sum_num < min_sum:   # 두 변수에 저장된 값 중 최소값을 최종 결과를 저장할 변수에 넣어줌
            min_sum = sum_num

    # 세로줄을 돌면서 탐색
    for i in range(N):
        if not visited[i]:      # 방문하지 않았을 경우
            visited[i] = 1      # 방문했다고 표시
            sum_num += num_list[num][i]     # 현재 인덱스 위치의 값울 임시 합 변수에 저장함
            find_sum(num + 1)       # 다음 줄로 넘어가서 확인
            visited[i] = 0          # 확인이 끝나고 방문 표시와 앞서 더해줌 값을 다시 빼줌
            sum_num -= num_list[num][i]


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    num_list = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N       # 방문 표시를 할 리스트
    sum_num = 0             # 임시 합을 저장할 변수
    min_sum = 10 * N        # 최솟값을 저장할 변수
    find_sum(0)             # 함수 호출

    print(f'#{tc} {min_sum}')

풀이 방법

dfs를 활용하여 풀이하였고 문제 조건 상 세로 줄에서 하나 이상의 수를 선택할 수 없기 때문에 세로줄을 기준으로 풀이하였다. 계속해서 탐색을 진행하면서 변수에 합계를 저장해주고 변수에 저장한 합계가 최종 출력할 결과값의 변수보다 작으면 값을 갱신해주는 방식으로 풀이했다.