[swea] 5189. 전자카트 / python 파이썬

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

 

thinking

아 문제 제대로 안읽어서 지존 오래걸렸다 . . . 😑

문제에서 말하듯, ( e[1][2]+e[2][3]+e[3][1] )

 1, 2 -> 2, 3 -> 3, 1  의 순서로 진행되기 때문에 현재 y인덱스(열)와 다음 시작하는 x인덱스(행)를 동일하게 두고 풀면 된다 ! !

이렇게 계속 이어지다가 처음 인덱스와 동일해지면 함수를 종료하면 된다.

최소값을 찾는 문제이므로 기존의 결과값보다 작은 경우에만 함수가 진행되도록 조건문을 걸어주었다.

처음 시작은 무조건 e[0][1] 또는 e[0][2] 또는 ... e[0][N-1] 이므로 range는 (1, N)까지로 처리했다.

 

코드

T = int(input())

# (current, next) = 0,1 -> 1,2 -> 2,0
def dfs(current, tmp):
    global res
    if tmp < res:
        if 0 not in visited[1:]:  # 전부 방문했다면
            res = min(res, tmp + a[current][0])  # 결과값 갱신하고 함수 종료
            return
        for next in range(1, N):
            if a[current][next] != 0 and visited[next] == 0:
                visited[next] = 1
                dfs(next, tmp + a[current][next])
                visited[next] = 0


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

    res = 10000
    for i in range(1, N):
        visited = [0] * N
        visited[i] = 1
        dfs(i, a[0][i])  # current_y, tmp_sum
    print("#{} {}".format(tc, res))