[ 백준 / 실버2+골드1 / 파이썬 Python ] 2098번 - 외판원 순회

링크 :
https://www.acmicpc.net/problem/10971
https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

10971번: 외판원 순회 2

---

코드 - 외판원 순회 2 ( 실버2 )

---

def DFS(start,node,total,visited):
    global answer
    if start == node and bin(visited).split("b")[1] == "1"*n:
        answer = min(answer,total)
        return
    for i in range(n):
        if visited & (1 << i) or W[node][i] == 0:
            continue
        DFS(start, i, total+W[node][i], visited | (1 << i))

n = int(input())
W = [list(map(int,input().split())) for _ in range(n)]
answer = 1e9
DFS(1,1,0,0)

print(answer)

 

풀이 - 외판원 순회 2 ( DFS, 백트래킹, 브루트포스 )

---

외판원 문제란, 여러 개의 도시를 방문하되 각 도시를 단 한 번씩만 방문하고 마지막에 시작점으로 돌아오는 최단 경로를 찾는 문제이다.

 

어떻게 보면 '최소 스패닝 트리'와 비슷하다고 생각이 들 수 있지만 서로 다른 문제이며 해결 방법도 다르다.

• 외판원 순회 문제는 최단 경로의 싸이클을 찾는 문제이며 싸이클이기 각 정점을 한 번씩만 방문하는 싸이클이기 때문에 정답으로 도출해낼 경로의 모든 정점은 두 개의 간선만을 가지게 된다.
• 최소 스패닝 트리는 모든 정점이 트리에 포함되어야 하기 때문에 각 정점에 대해 여러 개의 간선이 있을 수 있다. 한 부모에 여러 노드를 통합시키는 형식으로 진행한다.

백준에서는 도시의 개수 N의 크기에 따라 문제의 난이도를 다르게 측정하고 있다. 왜냐하면 N이 조금만 커지더라도 시간복잡도가 지수적으로 증가하여 고려해야할 사항이 많아지기 때문이다.

 

외판원 순회 2는 N의 최대 크기가 10으로 작은 편에 속하여 실버2의 난이도로 측정된 문제이다. 따라서 문제의 분류 또한 DFS와 백트래킹, 브루트포스로 표기되어 있다. 이 문제를 풀기 이전에 외판원 순회 (골드1)문제를 풀어보았지만 시간이 오래지나 기억이 나지 않아서 다시 풀게 되었다.

 

처음에는 한 지점에서 출발하여 다시 그 지점으로 돌아가야 하기 때문에 나는 이 한 지점을 정할 때부터 반복문을 써야 한다고 생각했다.

그런데 자꾸 시간초과가 발생했다. 생각해보니 외판원 순회 (골드1)을 해결할 때에도 똑같은 고민을 했었던 것 같았다.

다시 생각해보았다. 한 지점에서 출발하여 다시 그 지점으로 돌아간다는 말은 "모든 점을 통과하는 최단 경로로 이루어진 싸이클"이라는 말이다.

즉, 정답 경로에는 어떤 점을 선택하든 그 점은 포함되어 있을 것이기 때문에 어떤 점을 굳이 선택할 필요가 없었던  것이다. 따라서 아무 지점을 선택하여 DFS의 출발점으로 놓고 그 점으로 다시 돌아오는 최단경로의 싸이클만 찾으면 됐다.

 

DFS에서는 계속해서 주변에 가지를 뻗어 나가는데 이 가지마다 방문처리 배열이 달라진다. N이 10이라면 이 가지는 최대 10!정도의 크기까지 생성될 수 있기 때문에 모든 DFS에 방문처리 배열을 따로 저장할 수는 없다.

그래서 나는 시간복잡도도 줄이고 간단하게 방문처리를 할 수 있는 비트마스킹을 활용했다.

이 부분이 비트마스크를 활용하여 모든 점들을 방문하였는지 확인하는 코드이다.

bin(visited)는 방문처리 숫자를 이진법 문자열로 바꿔준다. ex) "0b11101"

이 문자열에서 이진수라는 의미를 가진 "0b"와 실제 비트가 표현된 "11101"을 분리하여 모든 비트가 1이라면 모든 점들이 방문한 것으로 판단하게 된다. 이렇게 비트마스크와 DFS를 사용하면 간단하게 낮은 크기의 N을 해결할 수 있다.

 

다음은 N이 16까지 올라갈 수 있는 외판원 순회 (골드1) 문제이다.

 

 

---

코드 - 외판원 순회 ( 골드1 )

---

import sys
input = sys.stdin.readline

def DFS(node,visited):
    if visited == (1 << (n-1)) - 1:
        if distance[node][0]:
            return distance[node][0]
        return INF
    if dp[node][visited] != 0:
        return dp[node][visited]
    dis = INF
    for i in range(1,n):
        if not distance[node][i] or visited & (1 << (i-1)):
            continue
        dis = min(dis, distance[node][i] + DFS(i, visited | (1 << (i-1))))
    dp[node][visited] = dis
    return dp[node][visited]

n = int(input())
INF = float('inf')
distance = [list(map(int,input().split())) for _ in range(n)]
dp = [[0] * (1 << n) for _ in range(n)]
print(DFS(0,0))

 

풀이 - 외판원 순회 ( DFS, DP )

---

외판원 순회 (골드1)는 N이 16까지 올라가여 시간복잡도가 외판원 순회 (실버2)에 비해 시간복잡도가 훨씬 높아지는 문제이다.

 

이 문제를 해결할 때에는 위에서 처럼 모든 가지를 다 탐색했다가는 시간복잡도가 O(16!)정도로 매우 커져 시간초과가 발생하게 된다. 따라서 탐색을 진행하다가 현재의 탐색이 최단경로가 아닌 것을 알게 되면 멈추고 다음 탐색을 이어나가야 한다.

 

현재의 탐색이 최단경로가 아닌 것은 어떻게 알 수 있을까? 답은 방문처리와 다이나믹 프로그래밍에 있다.

dp[node][visited]는 현재 node라는 점에 도착하였고 지금까지 visited만큼 방문했다는 뜻이다. 여기서 visited는 당연히 시간복잡도를 줄이기 위해 사용하는 비트마스크 숫자이다. dp[node][visited]의 값보다 현재 내가 가지고 있는 값이 더 크다면 똑같은 노드들을 방문했음에도 순서가 달라서 최단경로가 아님을 뜻한다. 이 때는 현재의 탐색경로가 최단경로가 아님을 깨닫고 탐색을 멈추게 된다. 이렇게 함으로써 불필요한 경로탐색을 줄여 최종적으로 시간복잡도를 크게 감소시킬 수 있다.

 

모든 경로를 탐색하고 나서는 마지막에 도착한 노드에서 출발지점으로 가는 길이 있는지 확인해야 한다.

만약에 출발지점(0)으로 가는 길이 있다면 그 값을 반환해주고 아니라면 무한대를 반환해주어 탐색을 무효화시켜주어야 한다.

최종적으로 모든 재귀를 거쳐서 가장 최단경로가 dis에 들어오게 된다.