[백준] 10971 외판원 순회2 파이썬 python

문제링크

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

10971번: 외판원 순회 2

 

코드

풀이1 itertools.permutations 사용 

import sys
from itertools import permutations
 
input = sys.stdin.readline
INF = 10*9
n = int(input())
w = [list(map(int,input().split())) for _ in range(n)]
 
all = permutations(list(range(n)))
 
ans = float('inf')
for p in all:
    cost = 0
    flag = True
    for i in range(n-1):
        tmp = w[p[i]][p[i+1]]
        if tmp == 0:
            flag = False
            break
        else: cost+=tmp
    tmp = w[p[n-1]][p[0]]
    if tmp ==0:
        flag = False
    else: cost+=tmp
    if flag and ans>cost:
        ans=cost
 
print(ans)
 

 

풀이2

import sys
input = sys.stdin.readline
 
n = int(input())
a = list(range(n))
w = [list(map(int, input().split())) for _ in  range(n)]
 
ans = float('inf')
 
def bf(start,next, cost, visited):
    global ans
    if len(visited)==n:
        tmp = w[next][start]
        if tmp !=0:
            ans = min(ans, cost+tmp)
        return
    
    for i in range(n):
        tmp = w[next][i]
        if tmp!=0 and i not in visited and cost<ans:
            visited.append(i)
            bf(start, i, cost+tmp, visited)
            visited.pop()
        
 
for i in range(n):
    bf(i, i, 0, [i])
print(ans)
 
 

 

POINT

풀이1

itertools.permutations을 사용하여 가능한 모든 순열을 만들고, 각 경로별 cost를 비교하여 최소 비용을 구한다.

 

풀이2

bf(start,next, cost, visited) 함수를 구현하였다.

start는 순환 시작점, next는 경로 상 다음 순회할 지점, cost는 현재까지의 비용, visited는 방문한 점들의 리스트 이다.

 

 if tmp!=0 and i not in visited and cost<ans:

1) 다음 순회 지점(i)까지 경로가 존재하고,

2) 다음 순회할 지점이 visited에 존재하지 않으며(이전에 방문한 적 없음),
3) 현재까지의 cost에 다음 순회 지점 비용을 더한 값(cost + W[next][i])이 현재까지 탐색해본 경로로부터 구해진 최소 순회 비용(ans)보다 크지 않다면,
다음 순회 지점을 방문하는 방식이다.

 

visited.pop()의 의미는 특정 순회 지점을 방문했다고 가정한 경로 탐색이 끝났음을 의미한다.예를 들어, 1번 노드에서 1->2 혹은 1->3 으로의 이동이 가능할때, 1->2으로의 가능한 경로의 탐색을 마쳤으니 이제 2번 노드를 방문 기록에서 빼내고, 3번 노드 방문을 시도하는 것을 의미한다. 

 

풀이 2가 가능한 모든 순열을 생성하지 않는다는 점에서 풀이 1보다 코드 실행시간이 효율적임을 확인하였다.