[맛있는물회] <SWEA알고리즘> 4881번 "배열 최소 합"

문제 조건

---

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

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

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

2	1	2
5	8	5
7	2	2

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

 

Input

---

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

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

 

Output

---

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

 

생각한 아이디어

---

단순하게 Brute Force 완전탐색을 생각했다.

그렇게 DFS를 구현하고 완전탐색을 구현했다.

 

먼저 N * N의 값에서 idx를 j 좌표로 두고 하나씩 움직였다.

그리고 세로줄의 인덱스를 Vistied 리스트를 만들어서 방문한지 안한지 조사했다.

그렇게 DFS를 만들고 수행하니깐 시간초과가 떴다.

 

N의 최대값이 9라서 9^9 정도는 2초 안에 10개 테스트 케이스 진행할 수 있을줄 알았는데 안되더라.

 

이때 가장 중요한 점!!!!!

가지치기

Pruning 알고리즘이다.

만약 DFS 중에 SUM값이 MIN 보다 크다면 이후에는 더해서 계산할 필요가 없다는 것이다.

 

그렇게 Pruning 조건식을 추가하니깐 바로 Pass 되었다.

 

소스코드

def count(idx, visited, SUM):
    global MIN
    if idx >= N:
        if SUM < MIN:
            MIN = SUM
        return
    ###############################
    #가지치기 하는 것 매우중요!!
    #가지치기 안하고 완전탐색했는데 시간초과떴다. 
    #가지치기를 하니깐 바로  PASS,,,
    if SUM > MIN:
        return
    ##############################
    for k in range(0,N):
        if visited[k] == 0: #k번째 값에 접근한적이 없다면
            SUM += maze[idx][k]
            
            visited[k] = 1

            count(idx+1, visited, SUM)
            
            visited[k] = 0 #원상복구
            SUM -= maze[idx][k]


T = int(input())
for TC in range(1,T+1):
    N = int(input())
    maze = list()
    for i in range(N):
        arr = list(map(int,input().split()))
        maze.append(arr)
    

    visited = {}
    for i in range(0,N):
        visited[i] = 0
    SUM = 0
    MIN = 99999

    count(0, visited, SUM)

    print("#%d %d" %(TC, MIN))

 

*파이썬 문법 정리

- list 값을 바로 변경할 수 없다?

visited[k][1] = 1 이렇게 직접 변경이 불가능한 것 같다. 계속 에러가 발생하였다.

그래서 visited는 어짜피 key가 단일이라서 딕셔너리로 바꾸어서 진행하였다.

- map_list = [list(map(int, input().split())) for _ in range(N)]

어떤 분이 이렇게 코드를 쓰셨다. 나는 이렇게 길게 썼는데. 익숙해져 봐야겠따.

    maze = list()

    for i in range(N):

        arr = list(map(int,input().split()))

        maze.append(arr)

- use_check = [True for _ in range(N)]

이 부분도 나는 딕셔너리 초기화를 for문으로 했는데 이 분은 리스트 초기화를 이렇게 간단하게 했다.

    visited = {}

    for i in range(0,N):

        visited[i] = 0