[SW Expert Academy] 파이썬 SW문제해결 구현_2일차 : 최소합

*문제의 저작권은 SW Expert에 있습니다.
문제 링크 : https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

[문제]

N X N 행렬이 주어졌을 때, 맨 왼쪽 위에서 오른쪽 아래까지 이동하면서 칸에 써진 숫자의 합계가 최소가 되도록 하며 이때의 합계를 출력하는 프로그램

 

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 가로 세로 칸 수 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 10이하의 자연수가 주어진다. 3<=N<=13

 

[출력]

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

 

<Code>

#방향 이동에 사용

dx=[0,1]
dy=[1,0]

#dfs함수 구현

def DFS(x,y,s):
    global min
    s+=graph[x][y] # 행렬 값을 더함
    if s > min: return #전체 더한 값이 최소합보다 크면 종료
    
    # 행렬 끝까지 갔다면 합을 최소합으로 지정 후 종료
    if y==(size-1) and x==(size-1) :
        min = s
        return
        
    # dx의 크기만큼 돌면서 오른쪽으로 이동하다가 막히면 아래쪽으로 이동
    for i in range(len(dx)):
        nextx = x+dx[i]
        nexty = y+dy[i]
        if nextx < size and nexty < size:
            DFS(nextx, nexty, s)

for i in range(1,int(input())+1):
    size = int(input())
    graph = [list(map(int, input().split())) for _ in range(size)]
    min = 13*13*10+1    #전체 합의 최대값
    DFS(0,0,0)
    print(f"#{i} {min}")