[python] 백준 10971번: 외판원 순회 2

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

[완전탐색]

외판원 순회2의 경우, 도시의 수가 최대 10개로 완전 탐색으로 풀어도 문제없이 동작한다. 

모든 노드가 서로 연결되어있다고 가정했을 때, 시간복잡도는 O(n!)이 된다.

n = 10이므로 10! = 3628800으로 시간 초과가 발생하지 않는다.

만약 n이 12이상으로 주어지 경우 연산 횟수는 대략 5억으로 시간초과가 발생한다는 점을 주의하자.  

완전탐색이라 permutation 모듈을 사용하는 방법도 있지만 백트래킹을 사용하여 풀어보았다.

def dfs(node, cost, arr, count):
    global visited, answer

    if count == n:
        first = arr[0]; last = arr[-1]
        check = False
        for _c, _n in graph[last]:
            if _n == first:
                cost += _c
                check = True
                break
        if not check:
            return
        answer = min(answer, cost)
        return

    for next_cost, next_node in graph[node]:
        if not visited[next_node]:
            visited[next_node] = True
            arr.append(next_node)
            dfs(next_node, cost+next_cost, arr, count+1)
            visited[next_node] = False
            arr.pop()


n = int(input())
graph = [[] for _ in range(n+1)]
answer = 1e9

for a in range(1, n+1):
    lst = list(map(int, input().split()))
    for i in range(n):
        b = i+1; c = lst[i]
        if a == b: continue
        if c == 0: continue
        graph[a].append((c, b))

for a in range(1, n+1):
    visited = [False for _ in range(n+1)]
    visited[a] = True
    dfs(a, 0, [a], 1)
print(answer)

 

* 처음에 틀린 이유) i에서 j로 방문할수 없는 경우 w[i][j] = 0으로 주어진다는 언급을 놓쳤다. 

                             if c == 0: continue 를 추가하여 방문할 수 없는 경우는 graph에서 제외해주었고

                             마지막 노드에서 첫노드로 돌아갈 때 경로가 없다면 무시하도록 check 변수를 사용하였다.

 

* 반례 

4
0 1 2 3
2 0 3 0
3 0 0 0
1 2 3 0

답: 11

 

 

[코드 개선]

n = int(input())
W = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
answer = 1e9


def dfs(node, x, cost):
    global answer

    if x == n:
        if W[node][0]:
            answer = min(answer, cost + W[node][0])
        return

    for next_node in range(1, n):
        if W[node][next_node] and not visited[next_node]:
            visited[next_node] = True
            dfs(next_node, x + 1, cost + W[node][next_node])
            visited[next_node] = False


dfs(0, 1, 0)
print(answer)