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

문제

---

 

10971번: 외판원 순회 2

코드

---

My answer

import sys
from itertools import permutations

n,cost=int(input()),0
city,result=[],1000000*n
order=[i for i in range(n)]

for i in range(n):
    city.append(list(map(int,sys.stdin.readline().split())))

for i in permutations(order,n):
    if(city[i[-1]][i[0]]!=0):
        for j in range(n-1):
            if(city[i[j]][i[j+1]]==0):
                cost=0
                break
            cost+=city[i[j]][i[j+1]]
        if(cost!=0):
            cost+=city[i[-1]][i[0]]
            result=min(cost,result)
    cost=0
print(result)

Another answer

from itertools import permutations
from sys import stdin
N = int(stdin.readline())
per = list(permutations([(i+1) for i in range(N)], N))
data = []
for i in range(N):
    data.append(list(map(int, stdin.readline().split())))

result = 10 ** 10
for i in range(len(per)//N):
    result_tem = 0
    judge = True
    for j in range(N):
        if data[(per[i][j]) - 1][(per[i][(j+1) % N]) - 1] == 0:
            judge = False
        result_tem += data[(per[i][j]) - 1][(per[i][(j+1) % N]) - 1]
    if result_tem < result and judge:
        result = result_tem
print(result)

 

풀이

---

우선 내 코드는 pypy에서는 돌아갔지만 python3에서는 시간초과가 떴다...python3으로 해결해보려했으나 pypy로 돌아가면 그냥 pass하라는 어떤분의 답변으로 그냥 넘어가기로했다. python으로 성공한 답변들중 내것과 가장 유사한걸 another answer에 올려놨는데 어떻게 한건지 모르겠다.. 내코드와 어느 부분이 다른거지?.. 우선 judge는 나는 cost=0으로 만듦으로써 따로 체크안해줘도됐고 어디가 문젠지 모겠다.. 반복문에서 len(per)//N인것 같은데 이 코드가 무엇을 의미하는지 모르겠다. 다른분의 코드에서도 아래코드를 작성한뒤 반복문을 돌리니까 돌아가던데 이해를 못했다.. 아래코드만 사용해서 내 코드를 바꾸면 python으로도 통과과 된다..

path = permutation[:len(permutation) // n]

 

import sys
from itertools import permutations

n,cost=int(input()),0
city,result=[],1000000*n
order=[i for i in range(n)]

for i in range(n):
    city.append(list(map(int,sys.stdin.readline().split())))
permutation = list(permutations(list(range(0, n ))))
path = permutation[:len(permutation) // n]

for i in path:
    if(city[i[-1]][i[0]]!=0):
        for j in range(n-1):
            if(city[i[j]][i[j+1]]==0):
                cost=0
                break
            cost+=city[i[j]][i[j+1]]
        if(cost!=0):
            cost+=city[i[-1]][i[0]]
            #result=min(cost,result)
            if(result>cost):
                result=cost
    cost=0
print(result)