문제 코드
from itertools import permutations
N = int(input())
graph = [[0 for col in range(N)]for row in range(N)]
for i in range(N):
num_list = list(map(int,input().split()))
for j in range(N):
graph[i][j] = num_list[j]
if num_list[j] == 0 :
graph[i][j] = float('INF')
max_count = float('INF')
move = []
for i in range(N):
move.append(i)
move_list = list(permutations(move,N))
for move in move_list:
count = 0
continue_point = False
for j in range(len(move)-1):
count += graph[move[j]][move[j+1]]
if count > max_count:
continue_point= True
break
if continue_point:
continue
count += graph[move[j+1]][move[0]]
if count < max_count:
max_count = count
print(max_count)
문제풀이
- 주어진 도시의 개수가 충분히 적어 브루트포스가 가능할것으로 판단
- 도시의 순열을 구해서 길이값을 더하고 가장 길이가 작은것을 넣도록 함
- 처음 제출시 시간초과 문제 발생 -> Count를 계산할때 이미 max보다 큰경우는 프루닝 하도록함
- 예시에서는 도시간 거리가 없는것이 0으로 나오므로 이부분을 inf로 바꿔서 수행