[SWEA 4881][파이썬 S/W 문제해결 기본]. 5일차 - 배열 최소 합

문제

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

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

 

 

 

 

내 생각

백트래킹문제이다. 완전탐색을 이용하면 시간초과에 걸릴 수도 !! 즉, Purning(가지치기)를 잘해야한다!!!!!!

이번 문제는 시간도 꽤 걸리고, Pass하기까지 고난과 역경이 있었다,,

N과 N줄의 matrix 입력받기, 방문했는지 체크하기

min_num 최솟값을 global로 선언

가지치기에서는 최솟값이 total보다 작을 때 함수 끝내기 (return)

그리고 백트래킹을 이용하여 index가 배열길이 만큼 되었을 때 최솟값 비교!

처음에는 index가 N길이가 됐고, min_num이 total보다 크면 min_num=total그리고 함수를 끝냈다. 근데 10개 중에 6개만 Pass,,, 

이것도 맞긴 맞다 ! 근데 아마도 내 생각으로는 효율성에서 Fail이 뜨지 않았을까,, 생각해본다..

첫번째 코드의

if index == N:
    if min_num > total:
        min_num = total
        return

이 부분은 재귀 호출이 종료될 때마다 min_num을 검사하고 업데이트한다. 즉 모든 재귀 호출에서 검사하고 업데이트하기 때문에 불필요한 재귀호출이 있지 않았을까! 생각한다.

두번째 코드의

if min_num < total:
    return
if index == N:
    if min_num > total:
        min_num = total

이 부분은 조기 종료 조건을 분리해서 재귀 호출을 줄인 방법이다. min_num이 현재까지의 total보다 작은 경우 탐색하지 않고 return한다. 악 쉬운 문제이나 쉽지 않은 문제였다. 더 열심히 할 필요가 있다 !

 

 

 

 

내 코드

1. Fail 코드 (6/10) - 제한시간 초과

def backtrack(index, total):
    global min_num
    if index == N:
        if min_num > total:
            min_num = total
            return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            backtrack(index+1, total + matrix[index][i])  
            visited[i] = False

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    visited = [False] * N
    min_num = 1000
    backtrack(0, 0)
    print(f"#{test_case} {min_num}")

 

2. Pass

def backtrack(index, total):
    global min_num
    if min_num < total:
    	return
    if index == N:
    	if min_num > total:
    		min_num = total
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            backtrack(index+1, total + matrix[index][i])  
            visited[i] = False

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    visited = [False] * N
    min_num = 1000
    backtrack(0, 0)
    print(f"#{test_case} {min_num}")