SWE(최소합)

작성일 | In

SWE 최소합

def isSafe(y, x):
    return 0 <= x < N and 0 <= y < N


def DFS(y, x):
    global sub_result, result
    if result < sub_result:
        return
    if y == N-1 and x == N-1:
        result = sub_result
        return
    for dir in range(2):
        newY = y + dy[dir]
        newX = x + dx[dir]
        if isSafe(newY, newX) and (newY, newX) not in visited:
            visited.append((newY, newX))
            sub_result += arr[newY][newX]
            DFS(newY, newX)
            visited.remove((newY, newX))
            sub_result -= arr[newY][newX]


for rounds in range(int(input())):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = []
    dy = [0, 1]  # 우 하
    dx = [1, 0]
    sub_result, result = arr[0][0], 999999999
    DFS(0, 0)
    print(f"#{rounds+1} {result}")

참고자료 [SWexperacademy]https://swexpertacademy.com [참고블로그]https://tothefullest08.github.io/algorithm/2019/08/01/1_5188_최소합/

0%