[백준] 파이썬 2098 - 외판원 순회

 

풀이.

비트마스킹을 이용해서 풀어야한다.

비트마스킹의 장점은 다음과 같이 3가지가 있다.

1. 빠른 수행시간

- 2진수를 이용하기에 연산속도가 빠르다

2. 적은 메모리

- [1, 1, 0, 0, 1, 1, 1] 같은 방문을 체크하는 배열을 1100111과 같은 이진수로 표현이 가능하다

3. 짧고 깔끔한 코드

 

우선 문제에서 살펴봐야하는 것은 도시에서 도시끼리의 길에 가중치가 있고 경로가 없을 수 있다는 것 그리고 처음의 경로로 돌아와야한다는 것이다.

즉 출발 지점에서 출발지점으로 돌아와야하므로 순환을 이룬다는 것이다.

또한 경로가 같으면 어떤 도시에서 출발하더라고 순회 비용은 동일하므로 무조건 0에서 출발하여 가장 작은 순회 비용을 구하면 된다.

 

소스코드.

 

 

 

	import sys
	def dfs(x, visited):
	# 도시를 모두 순환했을 때
	if visited == (1 << (n-1)) -1:
	if matrix[x][0]:
	return matrix[x][0]
	else:
	return inf
	if dp[x][visited] != -1:
	return dp[x][visited]
	dp[x][visited] = inf
	for i in range(1, n):
	# x 에서 i로 가는 경로가 없을 경우
	if not matrix[x][i]:
	continue
	# i에 이미 방문했을 경우
	if visited & ( 1 << i -1 ):
	continue
	dp[x][visited] = min(dp[x][visited], dfs(i, visited | (1 << (i-1))) + matrix[x][i])
	return dp[x][visited]
	input = sys.stdin.readline
	inf = float('inf')
	n = int(input())
	matrix = []
	for i in range(n):
	matrix.append(list(map(int, input().split())))
	dp = [[-1] * (1 << n) for i in range(n)]
	print(dfs(0, 0))

view raw 2098 - 외판원 순회.py hosted with ❤ by GitHub