[백준/Python]17182: 우주 탐사선

문제

https://www.acmicpc.net/problem/17182
백준 문제집 - 0x1C강 - 플로이드 알고리즘

 

알고리즘: 브루트포스 알고리즘, 최단 경로, 비트마스킹, 백트래킹, 플로이드-워셜

---

풀이

"모든 행성을 탐사하는데" 걸리는 최소 시간을 구해야한다.
단, 출발지로 돌아올 필요는 없으며 이미 방문한 행성도 "중복해서" 갈 수 있다.

 

👆 위 조건때문에 "최소 신장 트리" 문제인 줄 알았으나 결정적인 차이가 있다!
한 번 방문한 곳은 따로 비용이 발생하지 않는 최소 신장 트리와 달리, 재방문이 가능하긴 하지만 비용이 발생하는 구조다.

따라서 1) 플로이드 워셜로 각 행성간의 최단 경로를 구하고, 2) 방문하지 않은 행성들 중 현재 행성으로부터 소요 시간이 가장 짧은 행성을 선택한다.

 

참고로 DP(메모이제이션) + 비트마스킹을 적용하면 훨씬 빨라진다.
dp[curr][visited]: 현재 행성 curr에서 시작해서, 아직 방문하지 않은 모든 행성을 탐사하는데 필요한 최소 시간

• curr(현재 행성): 현재 탐사선이 위치한 행성 번호
• visited(방문 상태): 지금까지 방문한 행성들을 나타내는 비트마스크

 

실행 과정은 아래와 같다.

1. 모든 간선 a-b를 대상으로 플로이드 워셜 수행
2. 출발 행성 방문체크 후, 기점으로 DFS 실행
   • 모든 행성을 방문했다면 0 반환
   • DP에 [curr][visited]값이 있다면 해당 값 반환
   • 위 경우에 해당되지 않을 경우, 재귀적으로 DFS 실행
     • 아직 방문하지 않은 행성들을 하나씩 선택
     • 현재 행성-선택한 행성간의 거리값 + dfs(선택한 행성, 해당 행성을 방문처리한 visited)값 비교
     • 가장 최적의 값을 dp[curr][visited]값으로 저장
     • dp[curr][visited] 반환

 

전체 코드

# 메모리: 32412KB / 시간: 44ms
from sys import stdin


input = stdin.readline
INF = int(1e9)

N, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# 1. 플로이드-워셜로 두 행성간의 최단거리를 구해줌.
for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])

# 2. DP로 최적의 경로를 구함
# dp[curr][visited] = 현재 행성 curr에서 시작해서, 아직 방문하지 않은 모든 행성을 탐사하는데 필요한 최소 시간
dp = [[-1] * (1 << N) for _ in range(N)]

def find(curr, visited):
    if visited == (1 << N) - 1:
        return 0

    if dp[curr][visited] != -1:
        return dp[curr][visited]

    dp[curr][visited] = INF

    for nxt in range(N):
        # 방문하지 않은 행성일경우
        if not (visited & (1 << nxt)):
            cost = graph[curr][nxt] + find(nxt, visited | (1 << nxt))
            dp[curr][visited] = min(dp[curr][visited], cost)
    return dp[curr][visited]


print(find(K, 1 << K))

 

그리고 질문 게시판을 살펴보다가 발견한 글인데, DP 이해에 도움이 될 것 같다.

(출처:https://www.acmicpc.net/board/view/156743)

 

Q. "플로이드-워셜로 A → C가 A → B → C로 갱신되었는데, A에서 시작해서 C를 방문한다면 A -> B -> C를 방문한 것이 되는데... 왜 B를 따로 방문처리 해줘야 하나요?"

 

A. 구현 방식에 따라 차이가 있을것 같지만
dp[현재행성][방문한 행성들] 과 같이 선언하고, 현재 행성에서 이동할 수 있는 다음행성들을 모두 바라보도록 했다면
A → B → C로 실제로 이동했다고 해서 B를 고려하는 것은 불필요한 행동이라고 생각됩니다.
모든 경우의 수를 바라보게 되면 A → B 이동 B → C 이동하는 경우가 있을테니깐요

 

 

질문글 덕(?)에 나도 헷갈리는데... 결론은 플로이드 워셜에서의 A → C 갱신(A→B→C)과 DP에서의 방문처리는 별개인 것.

그리고 어차피 DP가 알아서 전체적으로 더 효율적인 최적의 값을 선택한다.