Baekjoon10971 - 외판원 순회2(Python)

백준 사이트 10971 - 외판원 순회2 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

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

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

코딩테스트 준비-기초 : 브루트포스 - 순열 문제입니다.

---

☑️ 4. 생각한 것들

• 최대 10!의 경우의 수가 있어서 효율성에러가 뜰 줄 알았는데 다행히 뜨지 않았습니다.
• 경로가 존재하지 않을 수(입력값이 0) 있으므로 그것에 대한 처리를 해줘야합니다.
• 또한 경로를 다 돌고 다시 최초의 자리로 돌아갈때도 입력값이 0일 수 있으므로 그거에 대한 처리도 해줘야합니다.

---

5. code

from itertools import permutations
from collections import deque

n = int(input())
travel_map = deque()
result_sum = 10e9

load = [i for i in range(1, n + 1)]
for i in range(n):
    tmp_li = deque(map(int, input().split()))
    travel_map.append(tmp_li)

for result in permutations(load):
    tmp_sum = 0
    judge = False
    for i in range(len(result) - 1):
        data = travel_map[result[i] - 1][result[i + 1] - 1]
        if data <= 0:
            judge = True
            break
        tmp_sum += data
    cycle_data = travel_map[result[i + 1] - 1][result[0] - 1]
    if cycle_data == 0 or judge:
        continue
    tmp_sum += cycle_data
    result_sum = min(result_sum, tmp_sum)
print(result_sum)

---

6. 후기

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.