BOJ 10971번: 외판원 순회 2

 

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

dfs와 백트래킹을 이용하여 풀었는데 왜 틀리다고 나올까..  삽질하다가 마지막에 시작했던 노드로 다시 돌아오는 부분을 검사할 때 cnt==3이라고 조건을 달아둔 걸 발견했다. 당연히 N-1이라고  해야 하는 것을ㅠㅠ

 

import sys

N = int(sys.stdin.readline())
W = []
for _ in range(N):
    W.append(list(map(int, sys.stdin.readline().split())))

check = [False]*N
ans = 10**9
tmp = 0
cnt = 0

def dfs(i, start):
    global tmp, cnt, ans
    check[i] = True
    
    if (cnt==N-1):
        if (W[i][start]!=0):
            ans = min(ans, tmp+W[i][start])
        return

    for n in range(N):
        if (check[n] == False and W[i][n]!=0):
             tmp+=W[i][n]
             cnt+=1
             
             dfs(n, start)
             
             check[n] = False   
             tmp-=W[i][n]
             cnt-=1
    return

for i in range(N):
    dfs(i,i)
    check = [False]*N
    cnt = 0
    tmp = 0
print(ans)

pypy3 통과