백준 24519번 : Bottleneck TSP (Large) (Python)

출처 : https://www.acmicpc.net/problem/24519

n, m = map(int, input().split())
INF = int(1e8)
graph = [[INF] * n for _ in range(n)]
for _ in range(m) :
    u, v, c = map(int, input().split())
    graph[u-1][v-1] = c
dp = [[0] * (1 << n) for _ in range(n)]

def dp_dfs(now, visited) :
    # 모든 정점 다 순회했으면
    if visited == (1 << n) - 1 :
        # now에서 시작점으로 가는 비용 dp 테이블에 저장하고 반환
        dp[now][visited] = graph[now][0]
        return dp[now][visited]
    # 이미 방문했으면 비용 반환
    if dp[now][visited] :
        return dp[now][visited]
    # 현재 정점의 비용 초기화
    now_cost = INF
    # 시작점을 제외한 모든 정점 탐색
    for i in range(1, n) :
        # 현재 정점 now와 간선이 존재하고 방문하지 않은 정점 i 방문
        if graph[now][i] != INF and not visited & (1 << i) :
            # now에서 i를 거쳐 시작점까지 순회하는 비용 계산
            now_i_cost = max(dp_dfs(i, visited | (1 << i)), graph[now][i])
            # 현재 정점의 비용 갱신
            now_cost = min(now_cost, now_i_cost)
    # dp 테이블에 저장하고 반환
    dp[now][visited] = now_cost
    return dp[now][visited]

def get_route(now, visited) :
    # 총 길이 n의 경로 출력
    for _ in range(n) :
        # 현재 정점 출력
        print(now + 1, end=" ")
        # 시작점 제외한 모든 정점 탐색
        for i in range(1, n) :
            # 방문한적 없고, 비용이 동일한 정점 i 방문
            if not visited & (1 << i) and dp[now][visited] == max(dp[i][visited | (1 << i)], graph[now][i]) :
                    now = i
                    visited |= (1 << i)
                    break

answer = dp_dfs(0, 1)
if answer == INF :
    print(-1)
else :
    print(answer)
    get_route(0, 1)

외판원 순회(https://www.acmicpc.net/problem/2098)와 유사한 문제다.
재귀를 활용해 dp 테이블을 채운다.

 

현재 정점 now를 방문했고 지금까지 now를 포함해 bit로 표현된 집합 visited의 정점들을 방문했을 때,
dp[now][visited]를 나머지 정점들을 모두 방문하고 시작점으로 돌아올 때의 비용(최대비용 간선의 최소값)이라고 정의하자.
순회하는 경로가 있다면 시작점은 무엇이든 상관없기 때문에 편의상 0번 정점을 시작점으로 가정한다.

 

예를 들어 현재 2번 정점을 방문 중이고, 지금까지 0, 2, 4번 정점을 방문, 1, 3번 정점을 방문하지 않은 경우의 비용은 dp[2][10101]으로 표현한다.
dp[2][10101]를 구하기 위해선 바로 다음 정점으로 가는 비용을 따져봐야 한다.
남은 정점을 순회하기 위해서는 1번 정점을 먼저 거치거나 3번 정점을 먼저 거쳐야 한다.
1번 정점을 먼저 거칠 때의 비용은 2번 -> 1번 정점의 비용과 1번 정점에 도착한 후 끝까지 순회할 때의 비용을 비교한다.
즉 max(graph[2][1], dp[1][10111])가 된다.
마찬가지로 3번 정점을 먼저 거칠 때의 비용은 max(graph[2][1], dp[3][11101])이 된다.
가능한 두가지의 비용 중 최소값이 최종적인 dp[2][10101] 값이다.

 

따라서 now와 연결된 간선이 있고 아직 방문하지 않은 모든 정점 i에 대해
max(graph[now][i], dp[i][visited | (1 << i)])를 구해 그 중 최소값을 dp[now][visited]로 저장한다.
dp[i][visited | (1 << i)]를 바로 계산할 수 없기 때문에 dp[now][visited]를 구하는 함수를 dp_dfs(now, visited)로 정의하고 재귀적으로(dfs처럼) 함수를 호출한다.

모든 정점을 다 방문했다면 now에서 시작점으로 가는 비용을 반환한다.
처음에 인접행렬로 간선의 비용을 저장할 때 INF를 초기값으로 지정했기 때문에 now에서 시작점으로 갈 수 없으면 INF가 반환된다.

 

다음으로 경로를 구한다.
처음부터 dp 테이블에 경로까지 저장하려고 하면 시간초과가 발생한다.
시작점부터 방문한적 없고 비용이 동일한 정점을 방문하면서 방문한 정점 총 n개를 하나씩 출력한다.

 

다른 조건은 동일한데 n이 작은 24512번 문제(https://www.acmicpc.net/problem/24512)는 간단한 백트래킹으로도 답을 구할 수 있다.

 

 

 

18번이나 헤딩하긴 했지만 어쨌든 푼 사람이 둘 밖에 없는 문제를 풀어서 뿌듯하다 ㅎㅎㅎㅎ