백준 2098 tsp

외판원순회(백준 2098)

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

이전에 비슷한 tsp 문제를 풀었던 것 같아
해당하는 ‘완전탐색’법으로 시도하는 방법은 시간초과가 되었기에
고민하다 결국 블로그를 보았다
비트마스킹과 DFS 를 활용하였고,
DP를 통해 중복 계산을 하지 않은 방식이였다
도시의 수가 많아질수록, 배열의 사용이
메모리를 많이 잡아먹게 되므로
(정확히는 dp로 저장하게 되는 배열)
비트 마스킹을 사용하였고,
‘같은’ 연산인 경우를 반환하고 싶기에,
dp 에 visited 도 같이 저장
이미 방문했다면, dp 딕셔너리에서 해당 값을 반환

dp 딕셔너리에, ‘(도시, 방문한 리스트(비트마스크))’ 의 key로
‘현재 도시까지의 최소 비용’을 저장한다는 점이 핵심인 것 같다

결국 1에서 다른 도시를 전부 방문하더라도,
해당 도시 방문 비용은 ‘DFS 반환 후’에 적용되며,
이에 따라 미리 저장해둔 ‘모든 도시 방문’이 존재하는 경우
해당 값과 비교하기에, 시작 도시를 고정해도 된다는 뜻

Code

import sys
import math

N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

dp = {}


def DFS(now, visited):
    # 모든 도시를 방문한 경우
    if visited == (1 << N) - 1:
        # 다시 출발 도시로 갈 수 있는 경우 출발 도시까지의 비용 반환
        if graph[now][0]:
            return graph[now][0]
        else:
            # 갈 수 없는 경우 무한대 반환 (이 경로가 최소비용으로 채택되지 않게)
            return math.inf

    # 이전에 계산된 경우 결과 반환
    # visited 도 확인
    if (now, visited) in dp:
        return dp[(now, visited)] # now까지 방문한 최소 비용

    min_cost = math.inf
    for next in range(1, N):
        # 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
        if graph[now][next] == 0 or visited & (1 << next):
            continue
        # 방문하며, visited에 '방문한'표시를 해주어 넘겨준다
        # 반환값에 그래프 가중치를 더해 cost에 저장
        cost = DFS(next, visited | (1 << next)) + graph[now][next]
        min_cost = min(cost, min_cost)

    dp[(now, visited)] = min_cost  # 현재도시까지 방문한 경우 중에서 최소 비용이 드는 루트의 비용 저장
    return min_cost  # 현재도시까지 방문하는 비용 리턴


print(DFS(0, 1))  # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리

해결 아이디어

1. DFS를 통해 탐색하며,
   비트 마스킹을 통해,
   모든 도시를 탐색하였는지, 이미 방문한 도시인지 확인한다
2. 모든 도시를 탐색했을 시,
   원래 도시로 가는 비용을 반환
   다만 갈 수 없다면 해당 경로는 목적지에 도달할 수 없으므로,
   무한의 가중치를 넣는다
   
3. 다음 도시에 dfs를 돌려,
   나온 반환값을 해당 가중치와 함께 저장하며,
   이를 ‘최소 가중치’와 비교한다
   
4. 모든 인접 도시를 탐색 하였다면,
   dfs를 종료한다