백준 10971번 외판원 순회 2

https://www.acmicpc.net/problem/10971
실패이유: 구현실패

def next_permutation(a: list):
    tail = len(a) - 1

    while tail > 0 and a[tail - 1] >= a[tail]:
        tail -= 1

    if tail == 0:
        return False

    change = len(a) - 1
    while a[tail - 1] >= a[change]:
        change -= 1

    a[tail - 1], a[change] = a[change], a[tail - 1]
    a[tail:] = reversed(a[tail:])
    return True


# w[i][j] = i -> j 로 가는 비용

n = int(input())
w = [list(map(int, input().split())) for _ in range(n)]
ans = 15000000
d = list(range(n))  # 도시번호를 순열로 표현

while True:
    if d[0] != 0:  # 순열의 첫번째 숫자를 0으로 고정, O(N * N!) -> O(N!)
        break

    cost = 0

    for i in range(n - 1):
        if w[d[i]][d[i + 1]] == 0:  # 못가는 도시인 경우
            cost = 15000000
            break
        else:
            cost += w[d[i]][d[i + 1]]

    if w[d[-1]][d[0]] != 0:
        cost += w[d[-1]][d[0]]
        ans = min(ans, cost)

    if not next_permutation(d):
        break

print(ans)

• 방문해야하는 도시가 겹쳐지지 않고, 순서를 고려하므로 ➔ 순열로 접근할 수 있다.
• d = list(range(n))
  • 도시번호를 순열로서 처리
• 0, 1, 2, 3, 1, 2, 3, 0, 2, 3, 0, 1, 3, 0, 1, 2 방문은 모두 같은 방문 방법이다.
  • 따라서 숫자 하나를 고정함으로써, 시간복잡도를 O(N * N!) ➔ O(N / (1/N) * N!) = O(N!) 로 낮출 수 있다.
• cost += w[d[-1]][d[0]]
  • 마지막엔 첫 번째 도시로 돌아가야 하므로 다시 돌아가는 비용을 추가해줘야 한다.

출처 : 코드플러스 - 알고리즘 기초 2/2 강의
https://code.plus/course/42