백준(Baekjoon) 2098번 : 외판원 순회 - python 풀이

🔴 문제 개요

🚀 난이도 : GOLD 1

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나입니다. TSP에 대한 자세한 설명은 위키피디아를 참고하시면 좋을 것 같습니다.

요약하자면 N개의 도시에서 모든 도시를 한 번만 거쳐 출발한 도시로 다시 돌아오는 최소 경로의 길이를 찾는 문제입니다.

제한사항

• 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다.
• 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.
• 항상 순회할 수 있는 경우만 입력으로 주어진다.

🟠 Solution

DP 방법론의 적용

그래프 경로 탐색이니 간단하게 DFS, 백트래킹으로 답은 찾아낼 수 있습니다. 다만 시간 복잡도가 팩토리얼 단위이니, 도시가 많아지면 절대 적용할 수 없는 솔루션입니다. 해당 솔루션의 실제 시간 복잡도는 O(N!)이며, 이 솔루션으로는 BOJ - 외판원 순회 2 문제를 해결할 수 있습니다.

지난 문제들에서 다뤄왔던 것처럼, 그래프 탐색에서 DP 방법론을 적용하면 시간복잡도를 줄일 수 있습니다. 현재 탐색 상태를 이전에 계산한 적이 있다면 중복해서 계산하는 것이 되므로, 한 번 계산할 때 값을 저장해놓고, 이후에 해당 값을 참고하는 메모이제이션을 활용하는 것입니다.

다만, 이 문제에서는 메모이제이션을 위한 dp 테이블을 어떻게 정의하느냐가 관건입니다. 우선 dp 테이블의 값으로는, 현재 탐색 상태에서 이후 탐색할 모든 도시까지 경로 합의 최소 값으로 둘 수 있습니다.

위 문단에서 언급한 '현재 탐색 상태'는 특정 도시에 도달했을 때일 것입니다. 하지만 이 상태 또한 지금까지 어떤 도시를 방문해왔는가에 따라 다른 상태라고 볼 수 있습니다. 예를 들어 아래 두 상태는 2번 도시에 도달한 상태라 할지라도 서로 다른 것이죠.

• 0 -> 1 -> 2
• 0 -> 3 -> 5 -> 4 -> 2

그렇기 때문에 dp 테이블을 2차원으로 정의해서 DP[현재 도달한 도시][현재 탐색 상태]로 두어 이를 구분할 수 있습니다. 이 방법으로 시간 복잡도를 $O(N^2\times 2^n)$까지 줄일 수 있습니다. 아직 너무 큰 시간 복잡도지만 기존 팩토리얼 범위에서 지수 범위까지 낮출 수 있습니다.

DP 테이블에 활용할 인덱스에서 현재 도달한 도시는 1~N 까지의 수로 표현할 수 있겠지만, 현재 탐색 상태는 어떻게 인덱스로 활용할 수 있을까요?

비트마스킹

여기서 비트마스킹을 활용할 수 있습니다. 도시의 수 N이 5라고 가정했을 때, 도시의 탐색 상태는 2^5 = 32가지로 정의할 수 있습니다. 이는 비트 00000 ~ 11111 범위에 존재하는 수의 개수입니다. 즉, 5개의 도시 중 1번째, 3번째 도시에 방문한 상태를 00101로 정의하므로써 각 32가지의 상태를 표현할 수 있습니다. 이는 어차피 int로 번역돼서 0~31 사이의 값을 가지게 되니, 인덱스로 활용할 수 있는 것이죠. 이를 적용한 dp를 비트필드를 이용한 다이나믹 프로그래밍이라고도 합니다.

이를 위해서 비트 연산으로 집합을 표현하는 방법을 이해해야 합니다. 이는 전 게시글(비트 연산을 활용해 집합 표현하기)에 포스팅 되어있으니, 처음 접하신다면 이 게시글을 보고오시면 이해에 훨씬 도움이 될 것입니다.

code - init

import sys

sys.setrecursionlimit(10**6)
INF = int(1e9)

input = sys.stdin.readline

N = int(input().rstrip())
adj = [list(map(int, input().rstrip().split())) for _ in range(N)]
dp = [[-1 for _ in range((1 << N))] for _ in range(N)]

솔루션 코드 전 초기화 단계의 코드입니다. 여기서 중요한 건 dp 테이블의 초기화입니다. 위에서 언급한 것처럼 DP[현재 도달한 도시][현재 탐색 상태]의 2차원 배열로 dp 테이블을 정의했습니다. 비트 연산 1<<N 의 결과는 100000(2)이 되므로 32 입니다. 32가지 상태를 표현하기 위해 활용했으며, 값을 -1로 초기화하여 현재 해당 상태는 탐색되지 않았음을 나타냈습니다.

code - solution

def dfs(now: int, visited: int) -> int:
    if visited == (1 << N) - 1:  # 전부 방문한 상태
    	# 처음 도시로 돌아갈 수 있는 경우 경로 값 반환
        # 경로가 존재하지 없으면 갈 수 없음을 의미하는 INF 반환
        return adj[now][0] if adj[now][0] else INF

	# 이미 탐색되어있는 상태의 경우 메모이제이션 값 반환
    if dp[now][visited] != -1:
        return dp[now][visited]

	# 처음 탐색하는 상태의 경우 계산 후, 메모이제이션
    for nxt in range(1, N):
        if adj[now][nxt] and not visited & (1 << nxt):
            cost = adj[now][nxt] + dfs(nxt, visited | (1 << nxt))
            if dp[now][visited] == -1:
                dp[now][visited] = cost
            else:
                dp[now][visited] = min(dp[now][visited], cost)

    return dp[now][visited] if dp[now][visited] != -1 else INF


print(dfs(0, 1))  # 0번째 도시부터 출발

본격적인 dfs 탐색에서는 재귀가 활용됩니다. 메서드의 인자는 현재 탐색 상태(현재 도달 도시, 지금까지 방문한 도시)입니다.

먼저 모든 도시를 방문한 경우 마지막 도시에서 처음 도시로 돌아가는 경로의 값을 반환합니다. 이 때 경로가 존재하지 않을 수 있으므로, 갈 수 없는 경우에는 돌아갈 수 없음을 의미하는 INF 값을 반환합니다.

이미 탐색되어있는 상태의 경우에는 저장된 값을 그대로 반환해주면 됩니다. 위 두 경우가 아닌 처음 탐색하는 상태의 경우 다음 도시를 탐색하여 새롭게 메모이제이션 해야합니다. 다음 도시의 탐색은 경로가 존재하는 경우, 방문되지 않은 도시에 한해서 수행됩니다. visited & (1 << nxt) 는 nxt 번 비트가 1인지(도시가 방문 되었는지)를 판단하는 비트 집합 연산입니다.

경로가 존재하고, 아직 방문되지 않은 다음 도시라면, cost를 계산합니다. 다음 도시로 가는 경로 + 다음 도시를 방문한 상태로 재귀하는 방법으로 cost를 구해낼 수 있습니다. 이때 다음 재귀에 주는 인자로는 다음 도시에 방문한 상태임을 표현해주어야 합니다. visited | (1 << nxt)는 다음 nxt 번 비트를 1(방문 처리)로 만들어주는 비트 연산 집합입니다.

이 때, 모든 다음 상태로 전이하는 경우에서 최소 값을 저장해야 하므로, min 연산을 활용해 값을 비교해서 저장하도록 합니다. 특정 방문 상태를 비트열로 표현하여 인덱스로 활용하는 것 외에는 일반적인 dfs + dp와 같습니다.

최종적으로 dp에 값이 업데이트 된 경우인지 체크하여 해당 값을 반환합니다. 업데이트 되지 않았다면 INF를 반환해야 합니다. 경로가 존재하지 않을 수도 있기 때문에 기존 초기화 된 값이 반환되지 않도록 처리한 것입니다.

🟡 고찰

끝났습니다! 이번 문제를 통해서 비트열을 처음 활용했고 이전 포스팅과 더불어서 새롭게 정리할 수 있었습니다. 또한 요새 랜덤으로 백준 골드 문제를 돌리면서 DFS와 DP를 활용하는 문제를 굉장히 많이 접하는데, 해당 방법을 활용해 더 다양한 문제를 풀어낼 수 있을 것 같다는 생각이 들었습니다. 어쨌든 위에서 언급한 것처럼 방문 상태를 비트열로 표현하여 인덱스로 활용하는 것 외에는 일반적인 dfs + dp와 같기 때문입니다.

🙏 해당 포스팅에 정리된 개념 및 코드에 대한 질문과 피드백은 환영입니다!