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

 

풀이.

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

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

1. 빠른 수행시간

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

2. 적은 메모리

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

3. 짧고 깔끔한 코드

 

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

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

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

 

소스코드.