[백준] 10971_외판원 순회2 (Python)

10971_외판원 순회2 (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 10971번: 외판원 순회2

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

예제 입력 1
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1
35

(3) 코드

n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]

depth = 0
answer = 99999999
visited = []

def recursive_dfs(city, depth, sum_cost, start):
    global answer

    # 순회를 마친 경우
    if depth == n:
        answer = min(answer, sum_cost)
        return

    for target in range(0, n):
        # 시작 지점으로 중간에 가지않으며 
        # target 이 city 가 되는 경우를 제외하고 
        # target 이 방문하지 않은 곳인 경우이고
        # city 에서 target 으로 갈때 0인 경우를 제외
        if target != start and target != city and target not in visited and nums[city][target] != 0:
            visited.append(target)
            sum_cost += nums[city][target]
            recursive_dfs(target, depth+1, sum_cost, start)
            sum_cost -= nums[city][target]
            visited.pop()

        # 마지막으로 시작지점으로 되돌아가기만 하면 되는 경우
        # city 에서 start 으로 갈때 0인 경우를 제외
        elif depth == n-1 and target == start and nums[city][start] != 0:
            visited.append(start)
            sum_cost += nums[city][start]
            recursive_dfs(city, depth + 1, sum_cost, start)
            sum_cost -= nums[city][start]
            visited.pop()

for city in range(n):
    sum_cost = 0
    target = 0
    start = city
    recursive_dfs(city, depth, sum_cost, start)

print(answer)

(4) 정리

코드를 어떻게 쉽게 작성해야 하나 고민중..
변수명만 적절하게 작성해도 어떻게 동작하는지 쉽게 그려져서 변수명에 신경을 잘 써야겠다.

(5) 참고

참고 풀이
질문 답변