백준 2098번 외판원 순회 (Python)

1번부터 N번까지 N개의 도시가 있고 어떤 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아온느 순회 여행 경로를 찾아야합니다.

i 도시에서 j 도시로 이동할 때 드는 비용이 W[i][j]이고 W[i][j] != W[j][i] 일 수 있고, W[i][j]==0 일 경우 i 도시에서 j 도시로 가는 경로는 없다고 합니다.

순회 여행 경로 중 가장 적은 비용을 들이는 경로를 구하면 됩니다.

 

 

이번 문제의 경우 주어진 시간 내에 풀지 못해 풀이를 참고하고 다시 풀이하게 되었습니다...🥺

 

 

아이디어

아이디어 1. 어떤 도시를 출발지로 할 것인지

문제에서 항상 순회할 수 있는 경우만 입력으로 주어진다고 알려주었습니다. 그러므로 어떠한 경우에도 순회는 가능합니다.

1~N의 모든 도시를 순회하고, 마지막 도시를 거쳐 첫 번째 도시로 다시 건너오는 경로를 만들 때, 만약 1~5의 도시를 순회할 때 최소 경비인 경로가 1 -> 3 -> 5 -> 4 -> 2 -> 1 라고 가정해보도록 하겠습니다.

위와 같은 경로는 원형으로도 표시가 가능합니다.

예시 경로 그림

이렇게 표현할 경우 어디서 시작해야할지 가늠이 될 것이라고 생각합니다.

1번에서 시작할 경우나 3번에서 시작할 경우 모두 똑같은 경로를 나타내기 때문에 어떠한 도시에서 출발해도 최단 경로를 찾는 것은 똑같습니다. 그러므로 저는 편의상 1번 노드에서 출발해보도록 하겠습니다.

 

아이디어 2. dynamic programming 활용 방법

이번 문제의 경우 모든 경우를 탐색하도록 하면 시간 초과가 발생하게 됩니다. (15! 정도의 경우의 수가 존재하기 때문입니다.)

그러므로 dp를 통해 메모리에 최적의 경우의 수를 저장하고 이를 활용해서 실행 시간을 줄여주어야 합니다.

여기서 어떤 방식으로 dp에 저장하는 것이 모든 값을 저장할 수 있는지 생각했어야 합니다.

 

dp에는 현재 지점과 경로에 관해 표시해야하고, 이 경로를 통해 얻을 수 있는 최소 경비를 저장할 수 있어야 합니다.

그러므로, dp에 저장해야 되는 것은 어떤 도시와 해당 도시까지 온 경로를 알 때, 이 지점에서 최단 경비로 순환해서 시작 도시로 이동했을 때의 경비를 저장해주어야 합니다.

 

아이디어 3. 경로 표시 방법

dp에서 최소 경비를 value라 할 경우, key값에서 경로를 표시할 수 있어야 합니다.

경로와 같은 경우 비트마스킹을 통해 표시할 수 있습니다.

dp[(x,path)] 일 경우 현재 x도시에 있고, 현재까지 방문한 도시를 path를 통해 표시합니다.

 

위의 예시 경로 그림을 예로 들자면, N=5이고 x=3일 경우 path는 00101이 됩니다. 이처럼 이미 방문한 도시를 1로 표시해주는 2진수 표기법을 이용해서 path를 표시해줍니다.

 

dp[(x,path)]의 value 값은 path + 다음 경로들로 이동해서 순환 경로가 만들어질 때, 그 중 현재 지점 x에서 첫 번째 도시로의 최소 경비값이 저장됩니다.

 

아이디어 4. 탐색 방법

한 도시에서 갈 수 있는 모든 도시를 탐색하고, 해당 경로가 최소 경비를 얻을 수 있는 경로인지 확인하는 것이 더 중요하기 때문에 DFS를 통해 탐색하게 되었습니다.

 

풀이

풀이 1. 도시 0부터 탐색 시작

...

print(dfs(0,1)) // 답 출력

dfs 함수의 인자는 첫 번째 방문 도시, 현재까지 방문한 도시(2진수) 입니다.

 

풀이 2, 3 dp 활용, 경로 확인

dp = {}

def dfs(x, path):
    if (x,path) in dp:
        return dp[(x,path)]
    
    dp[(x,path)] = MAX_VALUE
    for i in range(1,N):  // x는 현재 도시, i는 이후 방문 도시
        if W[x][i]==0 or path & (1 << i): # x->i 경로가 없을 경우, 이미 i 도시를 방문한 경우
            continue
        
        # dfs를 통해 반환된 값과 현재 최소 경비 비교
        dp[(x, path)] = min(dp[(now,path)], dfs(i, path | (1 << i)) + W[x][i])
    
    return dp[(x, path)]

dp 안에 이미 현재 지점(x)과 현재 지점까지의 경로(path)로 이동해서 얻을 수 있는 최소 경비 비용을 가지고 있다면 해당 경비를 그냥 봔환해줍니다.

 

x지점에서 이동할 수 있는 모든 도시에서 이동할 수 있는 도시(i)로 이동합니다. 이동할 때, path에 현재 도시 x를 추가 해줍니다.

 

dfs의 반환값과 현재 도시에서 다음 도시로의 이동 경비를 더한 값과 현재 최소 경비를 비교하게 됩니다.

dfs의 반환값의 경우 해당 지점에서 이동해서 얻을 수 있는 최소 경비를 반환하게 됩니다.

 

 

풀이 4. dfs 재귀 호출 중단 조건

def dfs(x, path):
    global N
    if path == (1 << N) - 1:
        return W[x][0] if W[x][0] else MAX_VALUE

모든 도시를 이동했을 경우 path는 모든 비트가 1로 채워진 형태가 됩니다. 이는 1을 N번 왼쪽으로 shift 연산한 것에서 - 1 한 것과 동일합니다.

이 때, 현재 지점 x에서 출발 도시(0)로 돌아올 수 있는 경로가 있을 경우 해당 경로의 비용을 반환해줍니다.

 

 

 

 

 

해결

이번 문제는 스스로 풀이하지 못해 아쉬웠던 문제입니다. 그래도 비트마스킹을 통한 풀이방법에 대해 알게 되었기 때문에 다른 관련 문제에서는 한 번 적용해서 풀이해보고 싶게 되었습니다.