Python - [백준]10971-외판원 순회

출처

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

문제

유명한 외판원 순회 문제의 쉬운 버전이다.
완전탐색에 백트래킹 테크닉을 얹어서 해결하는 문제이다.

접근 방법

모든 경로에 대해 탐색을 하되, 가장 작은 비용을 계산하도록 하는 문제이다.

먼저,dfs를 활용하여 모든경로의 경우에 대해 탐색을 하도록 한다.

그냥 하면 시간이 오래 걸리기 때문에, 여기서 추가해야할 것은 만약 현재의 값이 이미 구해놓은 answer보다 작다면 그 경로는 유망하지 않기 때문에 탐색을 더 진행하지 않도록 하였다.

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
answer = sys.maxsize
def dfs(x,next,tmp, visited):
    global answer
    if len(visited) == n:
        if arr[next][x] != 0:
            answer = min(answer, tmp + arr[next][x])
    for i in range(n):
        if arr[next][i] != 0 and i not in visited and tmp < answer:
            visited.append(i)
            dfs(x, i,tmp + arr[next][i],visited)
            visited.pop()
    

for i in range(n):
    dfs(i,i,0,[i])
    
print(answer)