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

외판원 순회 2

아이디어

처음엔 그냥 bfs로 풀려고 했는데 하면 할 수록 조합을 이용해서 푸는게 좋겠다는 생각이 들었다.(완전 탐색 필요)
그래서 조합을 이용해서 재귀로 풀었다.
(backtracking을 이용하는 것이 더 좋을듯!)

(python3은 시간초과가 나고 pypy만 통과함)
(+ 그냥 이 코드 그대로 외판원 순회(골드1) 제출했는데 시간초과남 ㅎ)

시간 복잡도

코드

from collections import deque
import sys
input = sys.stdin.readline

# 경우의 수 만들기
def permutation(arr):
    global min_pay

    # 종료 조건
    if len(arr) == n:
        # 최소 비용으로 업데이트
        min_pay = min(min_pay, check(arr))
        return
    
    # 경우의 수 뽑기
    for i in range(n):
        if not visited[i]:
            arr.append(num[i])
            visited[i] = True
            # 재귀
            permutation(arr)
            
            # 재귀 끝나고
            arr.pop()
            visited[i] = False

# 비용 계산하기
def check(arr):
    pay = 0
    for i in range(n):
    	# 0이 아니면 비용 더해주기
        if city[arr[i] - 1][arr[(i + 1) % n] - 1] != 0:
            pay += city[arr[i] - 1][arr[(i + 1) % n] - 1]
        
        # 0이면 못가는 경로
        else:
            pay = 9999999
            break
    return pay


n = int(input())
city = [list(map(int, input().split())) for _ in range(n)]
num = [i for i in range(1, n + 1)]
visited = [False] * n
min_pay = 9999999

permutation([])
print(min_pay)