[swea] 5188. 최소합 / python 파이썬

🚩 브루트포스(완전탐색)

 

thinking

가능한 모든 경우를 구한다음, 최소값을 구하면 시간초과가 뜬다.

최악의 경우 (2N!/N!*N!)*T = 10,400,600*50 = 520,030,000 번의 연산을 해서 그런것 같다.

그래서 애초에 부분합이 결과값보다 크면 함수가 끝나도록 처리해줬다.

현재 좌표를 함수의 인자로 받아, 방문한적이 없다면 방문체크 후 합을 더하며 재귀적으로 함수가 돌아가도록 구성했다.

 

코드

T = int(input())

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

def dfs(x, y):
    global res, tmp
    if res < tmp:  # 현재 결과값 보다 크면 함수 끝나도록 -> 제한시간때문에 가지치기 해야함
        return
    if x == N-1 and y == N-1:
        res = tmp
        return
    for d in range(2):
        nx = x + dx[d]
        ny = y + dy[d]
        if nx<0 or nx>=N or ny<0 or ny>=N:
            continue
        if (nx, ny) not in visited:
            visited.append((nx, ny))  # 좌표 업로드
            tmp += a[nx][ny]
            dfs(nx, ny)
            tmp -= a[nx][ny]  # 원상복구
            visited.remove((nx, ny))


for tc in range(1, T+1):
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    visited = []
    res = 3000
    tmp = a[0][0]
    dfs(0, 0)  # 현재좌표
    print("#{} {}".format(tc, res))