[백준] 17182 파이썬

문제

---

• 백준 17182 (골드 3)

백준 17182

n개의 행성과, 행성 간 이동을 하는데 걸리는 시간을 의미하는 2차원 행렬이 주어질 때 행성 k에서 출발하였을 때 모든 행성을 탐사하기 위한 최소 시간을 출력하는 문제였다.
탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다는 것이 문제의 조건이였다.
n이 최대 10이라는 점에서 시간복잡도가 굉장히 널널한 문제였다.

내 코드

---

중복이 불가하다면 bfs나 dfs로 간단하게 해결가능할 것 같았는데 행성을 중복해서 갈 수 있다는 점이 어려웠다.
시간복잡도가 널널하다는 점에서 플로이드-워셜 알고리즘이 떠올랐고, 행성간 최소 이동 시간을 구하면 문제를 풀 수 있을 것 같아 해당 방식으로 구현해보았다.
우선 플로이드-워셜 알고리즘을 통해서 행성간 최소 이동 시간을 이차원 행렬에 업데이트해준다.
그리고 dfs를 활용하여서 모든 행성을 탐사하면서 최소 시간이면 result에 업데이트 해주는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
visited[k] = True
result = 10**9

for s in range(n):
    for a in range(n):
        for b in range(n):
            t[a][b] = min(t[a][b], t[a][s] + t[s][b])

def dfs(idx, time):
    global result
    if False not in visited:
        result = min(result, time)
        return

    for i in range(len(t[idx])):
        if not visited[i]:
            visited[i] = True
            dfs(i, time + t[idx][i])
            visited[i] = False
    
dfs(k, 0)
print(result)

위의 문제와 같이 시간 복잡도를 보고 두가지 이상의 알고리즘을 사용하는 것도 고려해야겠다는 생각이 들었다.