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

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

🔥 작성 코드

def sol(row, tot):
    global result

    # 행의 마지막을 지나왔으면 종료
    if row == N:
        # 종료 시 총 합이 더 작다면 결과값 갱신
        if result > tot:
            result = tot
        return

    # 해당 row에서 값 하나를 tot에 더하고 다음 행 전달
    for i in range(N):

        # 내려받은 v 확인, tot이 이미 result보다 커진 경우는 제외
        if v[i] == 0 and tot < result:
            # 해당 값을 v에 표시하고 tot 더해주고 다음 행에 전달
            v[i] = 1
            sol(row+1, tot+arr[row][i])
            v[i] = 0


# 입력
T = int(input())

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

    # column에서 중복을 피하기 위한 방문 배열,
    v = [0 for _ in range(N)]
    # NxN 배열에서 가장 큰 tot을 result 초기값으로 설정
    result = 10*N
    sol(0, 0)
    print(f'#{test_case} {result}')

 

⭕ 해설

1.  NxN 행렬에서 가로, 세로에 하나의 숫자씩 더했을 경우, 가장 작은 합을 구하는 문제입니다.
   • 예를 들어, 다음과 같은 3x3행렬에서의 답은 8
     • 2 1 2
     • 5 8 5
     • 7 2 2
2. 세로 방향의 중복을 피하기 위해 방문 배열 v를 만들고 N개의 원소를 0으로 초기화합니다.
3. 함수의 인자로는 행의 번호(0~N-1)와 총 합을 입력합니다.
4. for문을 돌면서 값을 더해주고 다음 행으로 보냅니다.
   • 다음 행으로 보낸 뒤에는 해당 위치 v를 다시 0으로 바꿉니다.
   • 다음 위치에서 다시 v를 1로 바꾸고 다음 행으로 보냅니다.
   • 0부터 N-1까지 반복
5. 함수의 인자로 전달된 행의 번호가 N이 되면 마지막 행을 돈 직후이므로 종료합니다.
6. 이 때 구해진 총합 중 최솟값을 출력합니다.