[SWEA] 4881_배열 최소 합 (백트랙킹 이용)

📕 문제

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

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

예를 들어 다음과 같이 배열이 주어진다.

2	1	2
5	8	5
7	2	2

이경우 1, 5, 2를 고르면 합이 8로 최소가 된다.

 

[입력]

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

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

 

[출력]

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

 

💡 풀이법

1. 현재 행을 의미하는 idx라는 변수와 현재까지의 합을 의미하는 total 변수를 매개변수로 하는 dfs 함수를 만듦.

2. 재귀함수의 종료조건은 idx = N . idx가 N이라는 소리는 모든 행을 돌았다는 소리.

3. 지금까지의 합이 answer(최소값을 저장해둔 변수)보다 크다면 바로 return(가지치기)

4. visited라는 리스트를 만들어서 지금까지 지나온 열들을 넣어줌

5. 0~N-1까지 돌면서 visited에 없으면 방문기록에 넣어주고 다음 재귀함수를 돌림.

(다음 재귀함수는 idx+1을 해주고 total에 현재 방문한 좌표의 값을 추가 한 후 돌림)

6. 재귀함수를 다 돌린후 방문 기록을 pop을 해줘야 현재 i를 빼고 다시 다른 i값으로 돌릴 수 있음.

 

def section_sum(idx, total):
    global answer

    if idx == N:
        if total < answer:
            answer = total
            return

    if total > answer:
        return

    for i in range(N):
        if i not in visited:
            visited.append(i)
            section_sum(idx+1, total+matrix[idx][i])
            visited.pop()

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    answer = 30
    visited = []
    section_sum(0, 0)
    print('#{} {}'.format(tc, answer))