[백준 - Python] 10971. 외판원 순회 2 (완전 탐색)

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

10971번: 외판원 순회 2

 

코드

import sys

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
ans = sys.maxsize
visited = [0] * N

def backtrack(start, now, value, cnt):
    global ans
    if cnt == N:  # 원하는 깊이까지 도달 시
        if a[now][start]:
            value += a[now][start]
            ans = min(ans, value)
            return

    for i in range(N):
        if not visited[i] and a[now][i]:
            visited[i] = 1
            backtrack(start, i, value + a[now][i], cnt + 1)
            visited[i] = 0


for i in range(N):
    visited[i] = 1
    backtrack(i, i, 0, 1)   # 처음 번호, 현재 번호, 합, 갯수
    visited[i] = 0
    
print(ans)

 

문제를 이해하는데에는 어려움이 없었지만

해결을 못해서 다른 분들의 코드를 참고했다.

 

그래프 표현 방식의

인접 행렬 방식과 인접 리스트 방식 중에서

인접 리스트 방식으로만 문제를 풀어봤는데,

인접 행렬 방식을 연습해 볼 수 있었던 것 같다.

 

기본적인 백트래킹 틀을 가져가면서,

원하는 깊이에 도달하였을 때,

출발했던 도시로 돌아오는 비용을 더해주고

기존에 저장되어 있던 값과 비교해서 작으면 갱신을 해준다.

 

문제에서 도시 i에서 도시 j로 갈 수 없는 경우도 있다고 했는데,

마지막 도시에서 출발 도시로 가는 경로가 없는 경우에 대한 처리를

if a[now][start] 조건문을 통해서 해주었다.

 

 

참고 자료

https://velog.io/@y7y1h13/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EB%B0%B1%EC%A4%80-10971%EB%B2%88-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-2python

https://ji-gwang.tistory.com/266