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

전에 풀었던 문제인데 2달전 재채점 때 틀려서 다시 풀어보았다.

다시 풀려니까 도저히 풀리질 않아서 외판원 순회 아이디어를 읽었는데도 모르겠었다.

그래서 결국 내가 전에 티스토리에 썼던 글을 보았는데, 신기하게 그걸 보니까 작성할 수 있었다.

나는 내가 제일 잘 아는건가ㅋㅋ

 

하지만 그 글에서 헷갈렸던 부분이 있어서 다시 정리하려고 한다.

---

1. 외판원 순회는 어디에서 시작해도 값이 같다.

"도시" 가 아니라 "간선" 을 기준으로 보면 바로 이해된다.

 

1-3-2-1 이 최적해라고 하자.

그럼 최적해를 구성하는 간선은

1-3

3-2

2-1

이렇게 3개이다.

 

만약 3에서 시작했다고 하면 최적해는

3-2-1-3

이렇게 된다.

 

최적해의 구성 간선은

3-2

2-1

1-3

순서만 다르지 아까와 똑같다.

따라서 어디에서 시작해도 외판원 순회의 최적해는 같다.

---

2. 중복은 뒤에 있다.

이 문제는 바텀-업보다 탑다운으로 생각하는 것이 더 편하다.

중복되는 값이 앞에 있는 것이 아니라 뒤에 있기 때문이다.

전에 내가 썼던 포스팅의 예시가 내게는 찰떡 예시였다.

 

1, 2, 3, 4, 5 이렇게 5개의 도시가 있다고 하자.

만약 이 문제를 브루트포스로 푼다고 하면

5개 도시의 방문순열을 쭉 나열해서 최적해를 찾으면 될 것이다.

 

보통 순열은 이렇게 된다.

 

1-2-3-4-5

1-2-3-5-4

...

 

이러면 앞에가 중복되는 것 아닌가요?

 

하지만 아쉽게도 앞이 중복되는 것은 재귀함수 특성상 굳이 저장하지 않아도 활용하게 된다.

1-2-3 을 방문한 상태에서 4도 방문해보고 5도 방문해보고, 방문할 수 있는건 다 해보기 때문이다.

즉 저장해도 나중에 쓸 일이 없다.

 

중요한 것은 뒤에 중복되는 것이다.

만약 16개의 도시가 있다고 해보자

그러면 이렇게 되는 경우도 있지 않을까?

 

1-2-3-4-5-6-7-...-16

1-2-3-5-4-6-7-...-16

 

여기에서 이 6~16이 반복된다.

1-2-3 은 한번 방문해놓으면

여기서부터 4도 가고 5도가고 6부터 16도 다 가면서 알아서 활용할 것이다.

 

하지만 저 6부터 16의 뒷부분은은

4를 방문한다음 6~16을 계산하고

5를 방문한다음 6~16을 계산하고

..

이렇게 반복작업을 계속할 것이다.

 

그래서 이 문제를 풀 때는 재귀로 다음과 같이 풀 것이다.

 

현재 방문한 도시가  5 일 때

다음 도시 6을 방문할 때의 최적해를 구하고

현재 방문한 도시가  4 일 때

다음 도시 6을 방문한 경우의 최적해를 구하고

..

이 최적해들 중에서 최소를 저장하자

 

이때 이 과정에서 구해놓은 최적해를 DP에 저장해놓으면 된다.

위 예시로 보면 6~16을 구해놓으면 다음에 이 값을 활용하기 위해 저장하는 것이다.

식으로는 이렇게 세울 수 있다.

 

DP[now_city][now_visit_state] = 

min( Distance[now_city][next_city] + DP[next_city][next_visit_state], ... )

{next_city : now_city에 연결된 도시 중 방문하지 않은 도시} 에 대해 반복하여 구한 값 중 최소

 

이때 DP[next_city][next_visit_state] 는 아직 방문해본적이 없다면 값을 모른다.

그래서 이 부분을 재귀 함수로 던져주어서 구하게 해놓고

언젠가 값을 돌려주면 그 값으로 현재 DP 테이블 값을 채운다.

 

나는 헷갈리는 부분이 이 부분이었다.

보통은 now_city 를 방문한 상태가 next_city를 방문한 상태보다 더 작은 상태인데

이 문제는 오히려 now_city 를 방문한 상태가 더 큰 상태이다.

 

now_city가 2라면 이는 아래 외판원 순회 경로에서 다음과 같은 범위에서의 값을 의미한다.

1-2-3-4-5-6-7-1

 

하지만 다음 도시 3을 방문한다면 아래와 같은 범위에서의 값을 의미하게 된다.

1-2-3-4-5-6-7-1

 

이렇게 범위가 점점 줄어드는 것이다.

그래서 이 방식이 탑다운 방식이 되는 것이다.

큰 범위를 더 작게 쪼개서 구하기 때문이다.

 

이 외판원 문제는 굉장히 유명한 문제로서

Traveling Salesman Problem : TSP 로 불린다.

아래 코드에서 TSP 함수가 이를 의미한다.

 

구현할 때 주의할 점은 첫 도시를 이미 방문한 상태로 놓고 풀어야 한다.

안그러면 1 -> 2 -> 1 같은 케이스도 발생한다.

 

하지만 이렇게 놓고 풀면 모든 도시를 다 방문했을 때

다시 첫번째 도시로 돌아오는 데 필요한 비용을 계산하지 않게 된다.

이 부분을 주의하면 된다.

 

여기까지만 보고 코드로 구현하면 이렇게 구현할 수 있다.

 

def is_connected_from_to(city1, city2):
    return distance[city1][city2] > 0

def is_visited(city, visit_state):
    return visit_state & (1 << city) > 0

def TSP(now_city, now_visit_state):
    if dp[now_city][now_visit_state] < INF:
        return dp[now_city][now_visit_state]

    if now_visit_state == VISIT_ALL:
        last_city = now_city
        if is_connected_from_to(last_city, START_CITY):
            return distance[last_city][START_CITY]
        else:
            return INF

    minimum = INF
    for next_city in range(city_count):
        if is_connected_from_to(now_city, next_city) and not is_visited(next_city, now_visit_state):
            next_visit_state = now_visit_state | (1 << next_city)
            move_value = distance[now_city][next_city]
            left_value = TSP(next_city, next_visit_state)
            minimum = min(minimum, move_value + left_value)

    if dp[now_city][now_visit_state] == INF:
        dp[now_city][now_visit_state] = minimum

    return minimum

city_count = int(input())
distance = [list(map(int, input().split())) for _ in range(city_count)]

START_CITY = 0
VISIT_ALL = (1 << city_count) - 1
INF = 9876543210

dp = [[INF for _ in range(2**city_count)] for _ in range(city_count)]
answer = INF

print(TSP(START_CITY, 1))

하지만 이렇게 풀면 시간초과를 받는다.

한번 더 최적화가 필요하다.

---

3. 구하지 못한 것도 결과다

minimum = INF
for next_city in range(city_count):
    if is_connected_from_to(now_city, next_city) and not is_visited(next_city, now_visit_state):
        next_visit_state = now_visit_state | (1 << next_city)
        move_value = distance[now_city][next_city]
        left_value = TSP(next_city, next_visit_state)
        minimum = min(minimum, move_value + left_value)

이 부분을 보자.

만약 now_city에서 연결된 다른 도시가 없다든지 (차라리 그런거면 낫지만)

기껏 재귀해서 열심히 구해놓은 left_value의 값이 전부 INF 라는 이유로

저 minimum 값을 구하지 못한 상황이라면 어떻게 될까?

 

이 경우 now_city, now_visit_state 상태로는 최적해가 없음을 알고 있게 된다.

하지만 위 코드는 이 정보를 저장하지 않고 있다.

 

물론 저장하지 않아도 답은 구할 수 있다.

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

 

매번 현재 (now_city, now_visit_state) 조합을 방문할 때마다

이 상태로는 최적해가 없음을 알고 있으면서도

최적해가 없다는 걸 저 반복문과 재귀문을 다 실행하고 나서야 알게 되기 때문이다.

 

그래서 최적해가 없음을 따로 나타내는 값을 써서 표시해준다.

이 문제에서 모든 가중치가 양수이기 때문에 -1로 표기 할 수 있겠다.

 

하지만 INF, -1  이렇게 2개가 있으면 뭐가 뭔지 헷갈린다.

적당한 이름을 지어서 아래와 같이 코딩하였다.

 

city_count = int(input())
START_CITY = 0
VISIT_ALL = (1 << city_count) - 1
UNSET = 9876543210
IMPOSSIBLE = -1

distance = [list(map(int, input().split())) for _ in range(city_count)]
dp = [[UNSET for _ in range(2**city_count)] for _ in range(city_count)]


def is_connected_from_to(city1, city2):
    return distance[city1][city2] > 0


def is_visited(city, visit_state):
    return visit_state & (1 << city) > 0


def TSP(now_city, now_visit_state):
    if dp[now_city][now_visit_state] != UNSET:
        return dp[now_city][now_visit_state]

    if now_visit_state == VISIT_ALL:
        last_city = now_city
        if is_connected_from_to(last_city, START_CITY):
            return distance[last_city][START_CITY]
        else:
            return IMPOSSIBLE

    minimum = UNSET
    for next_city in range(city_count):
        if is_connected_from_to(now_city, next_city) and not is_visited(next_city, now_visit_state):
            next_visit_state = now_visit_state | (1 << next_city)

            move_value = distance[now_city][next_city]
            left_value = TSP(next_city, next_visit_state)

            if left_value != IMPOSSIBLE:
                minimum = min(minimum, move_value + left_value)

    if minimum == UNSET:
        minimum = IMPOSSIBLE

    if dp[now_city][now_visit_state] == UNSET:
        dp[now_city][now_visit_state] = minimum

    return minimum


print(TSP(START_CITY, 1))

 

다른 사람 코드는 코드만 보고는 내용을 알기가 어려워서 힘들었는데

이 코드는 코드만으로 내용을 이해할 수 있는 코드였으면 좋겠다.