[백준] 2098 - 외판원 순환 (G1)

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

2098번: 외판원 순회

간만에 만난 진짜 너무 이해하기 어려웠던 문제이다.

이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..)

 

이 문제의 핵심은 3가지다.

1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다.

2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다.

3. 최소를 구할 때도 0을 조심하자.

---

1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다.

---

사실 이것도 처음엔 이해가 안됐다.

그 이유는 '시작점으로 돌아온다' 라는 걸 알면서도 생각을 못하고 있었기 때문이다.

 

1 2 3

2 3 1

3 1 2

이게 같다고..?

1>2 하고 3>1 이 다르면 1>2>3 하고 2>3>1 은 다른거 아닌가?

 

3개 노드에 대한 사이클이라 노드 3개를 깔아두고 생각해서 헷갈렸었다.

 

1>2

2>3

3>1

이렇게 3개의 경로를 생각하면 헷갈리지 않는다.

1 2 3 1 이 최적해면

2 3 1 2 도 최적해고

3 1 2 3 도 최적해다.

 

따라서 시작점을 어디로 잡아도 상관없다.

---

2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다.

---

최근에 비트필드를 이용한 DP 문제에 대한 공부를 했기 때문에, 이 문제를 충분히 풀 수 있다고 자신감에 차있어서

거침없이 떠오른 아이디어를 구현해 나갔다.

 

현재 방문한 도시가 now_city 고, 지금까지 방문한 도시 상태가 now_bit 일 때,

 

dp[next_city][now_bit | 1 << next_city] =

min(dp[next_city][now_bit | 1 << next_city], dp[now_city][now_bit] + graph[now_city][next_city])

 

 이게 내가 떠올린 첫번째 dp 식이었다.

다음에 방문할 도시의 dp는 거기에 이미 저장되어있던 값하고,

현재 도시에서 다음 도시로 가는 길 중 더 가까운 길이라고 생각했다.

어떻게보면 다익스트라랑 비슷하다.

(그래서 더 헷갈린건가..?)

 

이걸 이제 어디에 집어 넣을까 고민하다가 익숙하게 구현했던 BFS를 사용했다가는

덱에 너무 많은 값이 들어가 메모리가 딱봐도 터질게 뻔했다.

그래서 아ㅋㅋ 어차피 깊이가 최대 16이네? 하고 DFS를 돌리게 구현했다.

 

그리고 칼같은 시간초과를 받았다.

그 뒤로 정말 여러가지 뻘짓을 하다가 답을 봤는데, DP식이 이해가 안가서 멍했었다.

 

위 풀이대로 답을 구해도 답은 나온다.

하지만 시간이 굉장히 오래걸린다.

 

그 이유는 아래 예시로 설명할 수 있다.

첫번재 케이스에서 도시를 아래와 같은 순서로 방문했다고 해보자.

1 2 3 4 5

그 다음에 방문할 땐

1 3 2 4 5

이 순서로 방문할 것이다.

 

여기에서 4 5 를 방문하는 것이 겹친다.

지금은 도시가 5개라서 괜찮지만,

1 2 3 4 .... 16

1 3 2 4 .... 16

이렇게 순서가 나온다면..?

저 4~16까지 를 다시 연산해야한다.

 

그래서 저 "나중에 방문하는 순서"를 DP테이블에 저장해야한다.

나에겐 이게 이 문제의 정말 골치 아픈점이었다.

그동안 DP문제는 항상 바텀업으로 구현하는 것에 익숙했고,

과거에 기록했던 값을 이용해서 지금의 값을 결정하는 DP문제를 풀어왔기 때문이다.

 

근데 지금 이 상황은 미래에 필요한 값이 중복될 거라는 걸 캐치하고, 미래의 값을 저장해야한다.

그리고 DP식도 바뀐다. 미래의 값을 활용하기 위해 임의의 '중간 도시'를 경유하는 것을 떠올려야 하기 때문이다.

 

dp[now_city][now_bit] = 

min(graph[now_city][via_city] + dp[via_city][now_bit | 1 << via_city], ........ , {가능한 모든 via_city 중 최소} )

 

무조건 모든 도시를 방문해서 원래 도시로 돌아와야하니, 어쨌든 어떤 도시든지 반드시 방문을 해야한다.

따라서 현재 상태에서 방문할 수 있는 모든 다른 도시를 다 방문해본다.

그리고 각각의 방문한 상태에서 다시 외판원 최단 경로를 구하도록 시키고 현재값에 합친다.

 

현재 도시에서부터 순환하는 최소 값은

현재도시에서 다음도시로 가는 값 + 다음도시에서부터 순환하는 최소값

 

이때 다음도시에서부터 순환하는 최소값을 DP에 저장해두면 (가령 위에 예시에서 4 ... 16)

다음에 필요할 때 바로 가져다 쓸 수 있다.

그리고 이 값은 한번 최소로 결정되면 다시 바뀌지 않는다.

 

베이스 케이스는 now_bit == (1 << city_count) 일때 이다.

이 경우 모든 도시를 방문했으므로, 남은 최단경로는 해당도시에서 처음 시작점까지의 길이다.

---

이 문제는 그나마 탑다운 방식으로 구현하면 DP식이 잘 이해된다.

나중에 방문할 때 필요한 계산을 재귀로 떠넘기고, 그 값을 받아내서 사용하는게 탑다운 방식인데,

DP식이 미래의 값을 활용하는 DP식이기 때문이다.

 

따라서 이 문제를 바텀업으로 풀면 머리가 아파지기 시작한다..ㅋㅋ

앞에서 미리 저장해두고 바뀌지 않는 값을 가져다가 쓰는게 바텀업인데,

미리 저장해두고 바뀌지 않을 값이 나중에 쓸 미래의 값이라는 느낌.

미래를 정해두고 현재를 구하는 굉장히 어색한 느낌이다.

바텀업인데 거꾸로 바텀업하는 기분..

---

3. 최소를 구할 때도 0을 조심하자.

---

아까 base 케이스를 구할 때

 

베이스 케이스는 now_bit == (1 << city_count) 일때 이다.

이 경우 모든 도시를 방문했으므로, 남은 최단경로는 해당도시에서 처음 시작점까지의 길이다.

 

라고 했었다.

근데 이게 '최소값'을 구하는 경우다보니 실수하기 좋은게,, "이동할 수 없는 도시"의 인접행렬값을 0으로 주는 바람에

이동할 수 없는 도시에 대해 이동하면 베이스케이스로 0을 반환해서 무조건 최소값을 갱신하는 경우가 생겨버린다.

 

따라서 0에 대해서는 그냥 아무것도 반환하지 않도록 하거나,

인접행렬 자체의 값을 저장할 때, 이동할 수 없는 경우는 inf 값을 줘야한다.

개인적으로 후자가 더 직관적이기도 하고, 구현할 때 실수를 줄이는 좋은 방법인 것 같다.

---

따라서 내가 구현한 정답코드는 아래와 같다.

 

import sys
input = sys.stdin.readline


def DFS(now_city, now_bit):
    global city_count, VISIT_ALL

    if now_bit == VISIT_ALL:
        return graph[now_city][0]

    if dp[now_city][now_bit] < float("inf"):
        return dp[now_city][now_bit]

    result = float("inf")
    for via_city in range(city_count):  # 임의의 경유 도시에 대해
        bit_of_via_city = 1 << via_city
        if now_bit & bit_of_via_city == 0 and graph[now_city][via_city] > 0:  # 경유 도시를 방문하지 않았고, 지금도시에서 경유도시로 갈 수 있다면
            # 현재 도시에서 현재 상태로 가는 최단 외판원 경로는 min(현재 경로, 현재도시에서 굥유도시로 간다음, 경유도시에서 경유도시를 방문한 상태로 이동하는 경로의 최소값)
            min_dist = DFS(via_city, now_bit | bit_of_via_city)
            if min_dist == 0: # min_dist가 0 이란 얘기는 min_dist 경로가 존재하지 않는다는 얘기다.
                continue
            result = min(result, graph[now_city][via_city] + min_dist)

    dp[now_city][now_bit] = result
    return dp[now_city][now_bit]


city_count = int(input())
graph = []
VISIT_ALL = (1 << city_count) - 1
for _ in range(city_count):
    graph.append(list(map(int, input().split())))

dp = [[float("inf") for _ in range(1 << city_count)] for _ in range(city_count)]

print(DFS(0, 1))

#for i in range(city_count):
#    print(dp[i])