[백준-파이썬] 10971(Silver)/백트래킹 : 외판원 순회2

<문제출처>

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

10971번: 외판원 순회 2

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

시작점에서 출발한 후 모든 점을 한번씩 거쳐 다시 시작점으로 돌아올때 가능한 최단 거리를 구하시오.

 

<고민 끄적끄적>

모든 경우를 탐색하는 백트래킹 방식으로 할 수 있다.

가지치기 조건은 노드에서 노드로 가는길이 없다면 스탑!
그리고 현재까지 최단경로로 갱신된 값을 초가화면 거기서 또 스탑!

이 두가지 방식으로 백트래킹을 구현하였다.

 

 

최종코드

import sys; input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)] # 주의!!!  1->2노드는 인덱스로 0 ->1이다. 
visited = [False] * (n + 1)
min_value = sys.maxsize

def dfs(v, s, d):
    global min_value
    if (d == n):
        if arr[v-1][0] != 0:
            min_value = min(min_value, s + arr[v-1][0])
        return
    
    for i in range(2, n + 1):
        if not visited[i]:
            if arr[v-1][i-1] == 0:
                continue

            if (s + arr[v-1][i-1] > min_value):
                continue

            visited[i] = True
            dfs(i, s + arr[v-1][i-1], d + 1)
            visited[i] = False


visited[1] = True
dfs(1, 0, 1)
print(min_value)

-> 문제 해결 아이디어는 금방 떠올랐는데 백트래킹 구현력이 조금 부족한듯 하다.