[백준알고리즘] 10971번: 외판원 순회 2 -Python

[백준알고리즘] 10971번: 외판원 순회 2 -Python

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

10971번: 외판원 순회 2

두 가지 방법으로 문제를 풀었다.

 

첫 번째 방법은 처음에 푼 방식으로 말 그대로 완전 탐색을 위해서 모든 경우를 탐색하도록 했고, 두 번째 방법은 찾아보니 다들 비트 마스크를 이용해서 문제를 풀었길래 공부해서 다시 풀어본 방법이다.

 

1. 첫 번째 방법

첫 번째 방법은 말 그대로 완전 탐색을 위해서 모든 경우를 다 조사했다.

 

주어진 조건 중에서 주어지는 입력은 반드시 순회가 생긴다고 했기 때문에 조금 더 간단하게 생각할 수 있다.

그 중 하나는 순회가 생기기 때문에 출발점은 아무거나 하나를 선택하면 된다는 것이다. 어디를 선택을 하던지 결국 사이클이 형성되면 출발점은 의미가 없어지기 때문이다.

 

그냥 0을 시작점으로 잡고 연결되어 있는 지점으로 반복해서 연결을 하며 사이클이 완성되면 비용을 갱신해주었다.

import sys

def move(now, depth):
    global charge, ans
    if depth == n:
        if path[now][0] > 0:
            ans = min(ans, charge + path[now][0])
        return
    
    visit[now] = 1
    for l in link[now]:
        if not visit[l]:
            charge += path[now][l]
            move(l, depth+1)
            charge -= path[now][l]
    visit[now] = 0

n = int(sys.stdin.readline())
path = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visit = [0] * n
link = {}
charge, ans = 0, 10**7

for i in range(n):
    link[i] = []
    for j in range(n):
        if path[i][j] > 0:
            link[i].append(j)

move(0, 1)

print(ans)

 

 

2. 두 번째 방법

두 번째 방법은 비트마스크를 이용해서 문제를 풀었다. 비트마스크를 사용해서 문제를 풀 수 있는 대표적인 문제가 외판원 순회문제(TSP: Traveling Salesperson Problem)라고 한다.

 

비트마스크를 이용한 풀이 방법도 앞선 방법과 거의 유사하지만 DP를 통해서 문제를 해결하며, 메모이제이션의 개념이 사용되기 때문에 완전 탐색보다 시간을 더 줄일 수 있는 방법이다.

 

이번 문제에서는 N의 범위가 작았기 때문에 충분히 완전 탐색으로 해결할 수 있었지만, N이 커질 경우에는 비트마스크를 사용한 풀이가 필수적이라 생각된다.

 

비트마스크를 사용한 방법에 대한 자세한 설명은 아래 블로그를 통해 공부했고, 다른 여러 분들의 코드들을 참고했다.

https://withhamit.tistory.com/246

 

간단하게 DP를 이용하는 방법만 설명하자면 다음과 같다.

A, B, C, D, E 총 5개의 도시가 있다고 하자. A->B->C->D->E->A로 연결된 하나의 경로가 존재하고, A->C->B->D->E->A로 이어지는 경로가 하나 있다고 하자. 그렇다면 위에 파란색으로 표시한 것처럼 공통된 부분이 생기게 된다.

두 경로에서 모두 현재 D에 위치해 있다고 했을 때 이전에 A, B, C를 지나왔기 때문에 앞으로 E, A를 방문해야 한다는 공통점이 있다. 그렇다면 "D->E->A"를 한 가지 경우로 묶어서 다음에도 D에 도착을 했는데 A, B, C를 지나왔다면 "D->E->A"의 비용만 추가로 계산을 해주면 되는 것이다.

 

이렇게 비트마스크를 이용한 방법은 "D->E->A"처럼 중복해서 계산할 부분을 줄여줄 수 있는 방법을 제시하고 있다.

 

아래의 코드를 살펴보면 before가 여태까지 방문했던 노드들을 가리키고 있는 것을 알 수 있다.

before는 실제로 비트를 넘겨주는 것은 아니지만 비트 연산을 통해 방문했던 점들을 확인하는 용도로 사용되고 있다.

 

예를 들어 bit가 11111라고 하면, before는 31인 상태이다. 또 bit가 11111이라 하면 앞에서부터 순서대로 4, 3, 2, 1, 0번째의 노드를 가리키며 모든 비트가 1이기 때문에 현재 4, 3, 2, 1, 0번째 노드는 방문을 했다는 것을 의미한다.

마찬가지로 11001의 비트라고 한다면 before는 25인 상태이다. 그리고 4, 3, 0번째 노드는 이미 방문을 했고, 2, 1번째 노드는 아직 방문을 안 한 상태이다.

 

이것을 이용해 before == (1<<n) - 1로 모든 지점을 방문했는지 알 수 있다.

n이 5라면 1<<5 = 100000(2) = 32이다. 32-1 = 31 = 11111(2) 이기 때문에 0, 1, 2, 3, 4번째 노드 총 5개가 이미 방문한 상태라는 것을 알 수 있다.

 

따라서 find()를 호출할 때 넘겨주는 인자로는 현재 지점의 노드 번호와 현재 지점까지 포함된 방문했던 지점들이며, 반복문을 통해서 새로운 지점으로 이동을 하기 위해서는 before | (1<<i) 를 통해서 이동하려는 지점까지 포함된 비트마스크를 넘겨준다.

 

import sys

def find(now, before):
    # 남아있는 경로를 이미 방문한 적이 있음
    if dp[now][before]:
        return dp[now][before]
    
    # 모두 방문한 경우
    if before == (1<<n) - 1:
        return path[now][0] if path[now][0] > 0 else sys.maxsize

    # 현재 지점에서 이동할 수 있는 지점들을 탐색
    cost = sys.maxsize
    for i in range(1, n):
        if not (before>>i)%2 and path[now][i]:
            # i부터 0까지 순회를 만든 최소 비용
            tmp = find(i, before|(1<<i)) # before | (1<<i) == before + (1<<i)
            # (now~i), (i~0)의 합과 현재까지의 최소 비용과 비교
            cost = min(cost, tmp + path[now][i])

    # 메모이제이션
    dp[now][before] = cost
    return cost

n = int(sys.stdin.readline())
path = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0]*(1<<n) for _ in range(n)]

print(find(0, 1))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

[참고]

https://withhamit.tistory.com/246