10971. 외판원 순회 2

멍진이·2021년 7월 2일
0

백준 문제풀기

목록 보기
30/36

문제 코드

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로 바꿔서 수행
profile
개발하는 멍멍이

0개의 댓글