BOJ 10971 외판원 순회 2

https://www.acmicpc.net/problem/10971
시간 2초, 메모리 256MB
input :

• N (2 ≤ N ≤ 10)
• 비용 행렬 (1 <= 성분 <= 1,000,000 , 갈 수 없는 경우는 0)
• W[i][j]는 도시 i에서 j로 가기 위한 비용
• 항상 순회할 수 있는 경우만 입력

output :

• 순회에 필요한 최소 비용을 출력

조건 :

• 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다.
• 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외
• 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다.

---

분명.. 알고리즘은 비슷한데 매번 뭐 하나가 빠져서 틀림...

그냥 시작 노드를 (0 ~ n - 1)
반복문을 돌면서 1개씩 골라서 전부 체크하자.

조건으로 설정할 것들.
data[now][next_node] 값이 0이 아니여야 하고, next_node가 visit에 들어있으면 안 된다.
자기자신을 가리키는 것은 0이여서 처리가 가능하니 생각 안해도 된다.
모든 경우를 다 보기 위해서 dfs를 수행 할 떄 처럼 dfs가 나오고 나서 visit에서 pop()을 해 주어야 한다.

그리고 마지막 노드에서 start노드로 올수 있는 길이 존재해야 한다..

import sys
n = int(sys.stdin.readline())
data = []
for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    data.append(a)


def dfs(start, now, total, visit):
    global ret
    if len(visit) == n:
        if data[now][start] != 0:
            ret = min(ret, total + data[now][start])
        return

    for j in range(n):
        if data[now][j] != 0 and j not in visit:
            visit.append(j)
            dfs(start, j, total + data[now][j], visit)
            visit.pop()


ret = 9999999
for i in range(n):
    dfs(i, i, 0, [i])

print(ret)

나는 각 노드에서 최소 거리를 구해가지고 가장 작은 노드를 찾아서 가려고 했는데 틀렸다.. 그냥 완전 탐색이면 다 돌려 버려야 겠다.