[SWEA, 완전 검색] 전자카트

흠... 너무 오래걸렸다..
오래 걸린 이유는

• 아래와 같은 tc의 경우에 [0,1]인 18부터 시작할 경우
   우선 48,55 이렇게 두 가지 경로로 갈 수가 있는데 48로 가는 순간
   다시 0번째 행으로 가게 되어서 34를 조회하게 되는 경우가 발생하게 되는 것 때문에 너무 오래 걸렸다... 
• 0 18 34
  48 0 55
  18 7 0
• 그래서 1로 가지 않게 for문을 1, n으로 두고 
• 마지막에 cnt 가 n-2의 경우에 s행의 0번째 인덱스 값을 더해줘 해결하도록 했음.

 

def search(s, hap, cnt):
    global mx_hap
    if cnt == n-2:
        mx_hap = min(mx_hap, hap+arr[s][0])
        return
    if hap >= mx_hap: return
    for i in range(1,n):
        if arr[s][i] and not visited[i]: # 해당 값이 0이 아니고, 방문하지 않았다면
            visited[i] = 1
            search(i, hap+arr[s][i], cnt+1)
            visited[i] = 0
    return

for tc in range(1, int(input())+1):
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    visited = [0]*n
    mx_hap = 101*n
    for s in range(1, n):
        visited[s] = 1
        search(s, arr[0][s], 0)
        visited[s] = 0
    print('#%d'%tc, end=' ')
    print(mx_hap)