외판원 순회 ( 2098 번 )

2098번: 외판원 순회

 

---

🧠 알고리즘

• DP + 비트마스크를 이용한 외판원 문제

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 모든 도시를 정확히 한 번씩 방문하고 다시 시작점으로 돌아오는 최소 비용을 구한다.
• 각 도시 방문 여부를 비트마스크로 표현하고, 방문 순서마다 최소 비용을 DP로 계산한다.

 

[ 로직 요약 ]

• _tsp(node, visit_info) 함수 정의
  • node : 현재 위치
  • visit_info : 방문한 도시 정보 (비트마스크)
• 모든 도시를 방문했으면 시작점으로 돌아가는 비용 반환
• 이미 계산된 상태면 DP 테이블 값 반환
• 현재 도시에서 방문하지 않은 도시를 순회하며 최소 비용 갱신
• 최종 DP 테이블에서 dp[1][1]이 0번 도시부터 시작한 최소 비용

---

 

🧾 코드

import sys

def _tsp(node, visit_info):
    if visit_info == (1 << n) - 1: # 다 방문 완료 ~
        return map_list[node][0] if map_list[node][0] != 0 else float('inf')

    if dp[node + 1][visit_info] != -1:
        return dp[node + 1][visit_info]

    dp[node + 1][visit_info] = float('inf')
    for next in range(n):
        if map_list[node][next] != 0 and not visit_info & (1 << next): # 경로가 있으면 & 방문 안했으면
            dp[node + 1][visit_info] = min(_tsp(next, visit_info | (1 << next)) + map_list[node][next], dp[node + 1][visit_info])

    return dp[node + 1][visit_info]
            

n = int(sys.stdin.readline().rstrip())
map_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
"""
    dp[현재 노드][방문 정보 ( 비트 마스크 )]
    비트 마스크 : 1111
    value : 현재 cost
"""
dp = [[-1] * (1 << n) for _ in range(n + 1)]
_tsp(0, 1 << 0)

print(dp[1][1])

---

 

⏱️ 시간 복잡도

도시마다 2가지 방문상태 존재 ( 0, 1 >> 미방문, 방문 )
도시가 n개 경우.. 2 * 2 * 2 * ~~~ n번 ( 2 ** n )

해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( 2 ** n )