[BaekJoon] 백준 2098번 외판원 순회

[BaekJoon] 백준 2098번 외판원 순회

 

🎈문제

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

 

💬설명

간단하게 말하자면, 해당 문제는 사이클을 구하는데 그 사이클을 돌 때 가장 적은 비용이 드는 사이클을 구하는 것이다.

즉, 1->0->2->3->1 이렇게 돌아서 오는 경우와 2->3->1->0->2 이렇게 돌아서 오는 경우가 드는 비용이 같다는 것을 우선 염두에 두고 생각을 해보자. (편의상 0번 도시부터 있다고 가정하자.)

 

그렇게 되면, 우리는 모든 경우를 돌 때 0번 도시에서 출발한다고 가정해도 무방하다.

0->...->0 에서 ("..." 에 들어가는 도시들의 순서 + 모든 도시들을 돌았는지)만 고려해주면 되니까!

다시 말해서, 0번 도시에서 시작하는 경우만 생각하더라도 모든 경우의 수를 고려할 수 있다는 말이다.

 

그럼 0번에서 시작을 한 뒤에 이어서 나오는 도시들의 순서는 어떻게 정해야 할까?

도시들을 선택하는 방식에는 완전탐색을 이용할 수 있다.

물론 그렇게 되면 경로를 선택하는 과정에서 O(N!)이 되는데 이는 DP로 줄일 수 있다.

 

DP로 문제를 정의하게 되면 점화식은 다음과 같다.

dp[i][route] = (현재 위치가 i이고 지금까지 route를 거쳐서 왔을 때 드는 비용의 최소값)

# i 직전에 방문한 곳을 i-1이라고 하면
dp[i][route] = min(dp[i-1][route] + W[i-1][i])

점화식에 대해서 설명하자면,

외판원이 route에 해당하는 도시(route는 비트마스킹을 이용해서 정의하는데 이는 뒤에서 살펴보자)들을 방문하고 i번 도시에 현재 머물러 있다. 그때까지 든 비용의 최소값을 dp[i][route]라고 한다. 예를 들면, dp[3][111]인 경우, 외판원이 0->(1, 2 도시)->3 도시를 돌았을 경우 드는 최소 비용이다.

 

따라서 i번 도시 이전에 방문한 도시를 i-1 이라고 했을 때(무조건 i-1일 수는 없고 여기서는 편의상 i-1이라고 한다. 3번 도시에 방문했다고 이전에 방문한 도시가 무조건 2번 도시일 수는 없으니까!) dp[i-1][route]에 W[i-1][i](i-1번 도시에서 i번 도시로 갔을 때 드는 비용)를 더해준 값의 최소값이 dp[i][route]라고 할 수 있다. 여기서 최소값이라고 하는 이유는 i-1번 도시까지 방문했을 때 i번 도시는 미방문 도시들중 가장 적은 비용의 도시를 선택해야하기 때문이다.

 

결국 우리가 찾아야 하는 값은 dp[0][111...]이다. 현재 위치가 처음 출발했던 0번 도시 & 모든 도시를 다 방문해서 111... 인 경우이다.

 

그럼 여기서 모든 도시를 다 방문해서 111...이 된다고 했고, 그 위에서는 1, 2 도시를 돌았을 때 011이 된다고 했는데 이건 무슨 의미일까? 어느정도 눈치를 챘겠지만 이는 비트를 이용해 방문 여부를 표시한 것이다. 이렇게 0, 1을 이용해 집합에서 원소의 포함 여부를 표시하는 방식을 비트마스킹 기법이라고 한다. 비트마스킹을 이용하면 빠르고 적은 메모리로 방문여부를 구현할 수 있다.

 

👩‍💻코드

# BaekJoon 2098

# 입력값 초기화 & 배열 설정
N = int(input())
W = [[] for _ in range(N)]
dp = [[0 for _ in range(1 << N - 1)] for _ in range(N)]

for i in range(N):
    W[i] = list(map(int, input().split()))


# 현재 위치 i, 지금까지 방문한 도시들의 집합 route일 때 최소 비용 구하는 함수
def solution(i, route):
    global N, W, dp

    # 이미 방문한 경로면 memoization 해둔 값이므로 return
    if dp[i][route] != 0:
        return dp[i][route]

    # 모든 도시를 다 방문한 경우
    if route == (1 << (N - 1)) - 1:
        # 마지막 위치에서 0번 도시로 가는 경로가 없는 경우
        if not W[i][0]:
            return float('inf')
        # 마지막 위치에서 0번 도시로 가는 경로가 있는 경우 정답 반환
        else:
            return W[i][0]

    # 점화식을 토대로, 최소값을 찾아서 다음 방문 도시 선택하기
    min_price = float('inf')
    for j in range(1, N):
        # i번째 도시에서 j번째 도시로 가는 경로가 없는 경우
        if not W[i][j]:
            continue
        # j번째 도시가 이미 방문한 도시인 경우
        if route & (1 << j - 1):
            continue
        # j번째 도시를 방문했을 경우 비용 계산해서 최소값이면 선택
        # i -> j 도시 가는 비용 + solution(j번째 도시, j번째 도시를 추가한 경로)
        dist = W[i][j] + solution(j, route | (1 << (j - 1)))
        if min_price > dist:
            min_price = dist
    dp[i][route] = min_price
    return min_price


# 0번째 도시에서 출발, 아무 도시도 방문하기 않았기 때문에 0
print(solution(0, 0))

 

 

 

👉참고

https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-2098-%EC%99%B8%ED%8C%90%EC%9B%90%EC%88%9C%ED%9A%8C-Python

https://shoark7.github.io/programming/algorithm/solve-tsp-with-dynamic-programming