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

 

🚛 파이썬 SW문제해결 기본 - Stack2

• NxN 배열에서 세로당 하나의 숫자를 선택해 모두 더했을 때 최소의 합을 구하는 문제입니다.
• 같은 세로열에서 2개의 숫자를 선택할 수는 없습니다.

 

 

💡 아이디어

순열과 조합 문제, DFS를 구현하여 풀고 계산량을 줄이기 위해 가지치기 사용합니다.
가지치기를 하지 않으면 계산량초과로 오류가 발생하기 때문에 유의하여야 합니다.
한 세로열 당 방문함을 체크하고 다음 열로 넘어가는 코드를 신경써서 배치하였습니다.
백트래킹을 사용하여 좀 더 효율적인 코드를 완성하였습니다.

 

 

🎲 파이썬 코드

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

# TODO Learn 4881 배열최소합.

def per(k, midV):
    # 최솟값 가져오기.
    global minV
    # 가지치기.
    if minV < midV:
        return # return 받을 거 없을 때는 값 안적어줘도 됨.함수 끝내는 용도.
    # 재귀로 k가 배열 길이만큼 되었을때 최솟값 비교해서 구하기.
    # 백트래킹을 이용..
    if k == N:
        if minV > midV:
            minV = midV
    for i in range(N):
        # 세로열 당 1개씩이므로 방문한 곳 체크.
        if not visited[i]:
            #sel[k] = i
            visited[i] = True
            per(k+1, midV + BRD[k][i]) # 다음 열로 넘어감, 자리 중요.
            visited[i] = False

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    BRD = [list(map(int, input().split())) for _ in range(N)]

    minV = 1e1000000  # 최솟값 초기설정..
    visited = [False] * N # 방문한 곳 기록..
    #sel = [-1] * N  # : 순열 데이터
    per(0, 0)
    print('#{} {}'.format(tc, minV))

*제 코드가 정답은 아닙니다. 부족한 부분과 더 좋은 아이디어가 있으시면 댓글로 남겨주세요! :)