이번 문제는 플로이드-와샬과 백트레킹을 통해 해결하였다. 처음에는 비트마스킹을 활용하여 접근하였다. n이 10까지 가능하므로 2^10인 1024를 비트마스킹 범위로 지정하고, 방문처리를 할 때 visited[도착 행성][출발 행성]으로 지정하였고, 출발 행성을 비트마스킹으로 활용하여 모든 행성으로부터 한번씩은 방문할 수 있도록 구현하였다. 그러나 이 방법은 37%에서 시간초과가 발생하였다. 아무래도 하나의 정점에 최대 10번까지 방문할 수 있어 발생한 문제인 것 같았다.

처음에는 주어진 graph가 플로이드-와샬을 통해 나온 값이라고 생각하고 접근하였다. 그러나 플로이드-와샬 알고리즘을 돌려보니 더 짧은 거리를 구할 수 있었다. 플로이드-와샬을 통해 각 정점에서 각 정점으로의 최단 거리가 구해졌다면, 방문처리를 굳이 비트마스킹으로 하지 않아도 되었다. 그때 그때 방문한 방법이 최선의 방법이 되기 때문이었다. 그래서 플로이드-와샬을 통해 graph를 새롭게 갱신하고, 백트레킹을 통해 모든 정점을 방문하는 방식으로 해결하였다.

Code

처음 코드 (백트레킹 + 비트마스킹, 시간 초과)

n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False for _ in range(1024)] for _ in range(n)]
answer = 1e9
def find_min(cur, time, chk):
    global answer
    if chk == [True for _ in range(n)]:
        answer = min(answer, time)
        return
    if time > answer:
        return
    for i in range(n):
        if cur == i:
            continue
        if not visited[i][1<<cur]:
            visited[i][1<<cur] = True
            if chk[i]:
                find_min(i, time+graph[cur][i], chk)
            else:
                chk[i] = True
                find_min(i, time+graph[cur][i], chk)
                chk[i] = False
            visited[i][1<<cur] = False
visited[k][0] = True
chk = [False for _ in range(n)]
chk[k] = True
find_min(k, 0, chk)
print(answer)

정답 코드 (플로이드-와샬 + 백트레킹)

n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [False for _ in range(n)]
answer = 1e9
for d in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][d]+graph[d][j])
def find_min(cur, time, chk):
    global answer
    if chk == n:
        answer = min(answer, time)
        return
    for nxt in range(n):
        if not visited[nxt]:
            visited[nxt] = True
            find_min(nxt, time+graph[cur][nxt], chk+1)
            visited[nxt] = False
visited[k] = True
find_min(k, 0, 1)
print(answer)