백준 17182 우주 탐사선

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

각 지점마다의 최단거리를 구하고 백트래킹을 해주면 되는 문제이다.
최단거리를 구할땐 플로이드 워셜 알고리즘을 이용했다.
백트래킹시 상태관리를 해주어야 하는데,
노드가 몇개 없는 점에서 이전에 풀었던 카카오 기출문제가 생각났다.

https://school.programmers.co.kr/learn/courses/30/lessons/81304
프로그래머스 -미로 탈출

위의 문제에서도 현재 상태를 비트로 관리하는데, 노드가 10개라고 방문한 노드를 2^10 = 1024개로 표현할 수 있으니 편리했던 기억이 있다.

이점을 착안해 비트마스킹으로 완전탐색을 했다.

import math
n,k = list(map(int,input().split()))
dist = []
for i in range(n):
    dist.append(list(map(int,input().split()))) 
for p in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][p] + dist[p][j]:
                dist[i][j] = dist[i][p] + dist[p][j]
ans = math.inf
end = (1<<n) - 1
def func(visited,start,cost):
    global ans
    if visited == end:
        ans = min(ans,cost)
        return
    for node in range(n):
        if not visited & (1 << node): ## 해당 노드를 방문하지 않았다면
            new = visited | (1 << node)
            surcost = dist[start][node]
            func(new,node, cost + surcost)

func(end&(1<<k),k,0)
print(ans)