99클럽 코테 스터디 21일차 TIL - 우주 탐사선(백준 #17182)

❇️오늘의 학습 키워드 : 우주 탐사선(백준 #17182)

문제

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력

첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij  ≤ 1000)

출력

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

예제 입력 1 

3 0
0 30 1
1 0 29
28 1 0

예제 출력 1 

2

예제 입력 2 

4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

예제 출력 2 

74

정답 코드

n, k = map(int, input().split())
dp = [list(map(int, input().split())) for _ in range(n)]

# 플로이드-와샬 알고리즘 적용
for k in range(n):
    for i in range(n):
        for j in range(n):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = float('inf')
visited = [0] * n
visited[k] = 1

def dfs(node, cost, visited_count):
    global min_sum

    # 모든 노드를 방문한 경우
    if visited_count == n:
        ans = min(ans, cost)
        return

    # 현재 노드에서 다른 노드로 이동
    for next_node in range(n):
        if not visited[next_node]:  # 방문하지 않은 노드라면
            visited[next_node] = 1
            dfs(next_node, cost + dp[node][next_node], visited_count + 1)
            visited[next_node] = 0  # 백트래킹

# 시작 노드에서 탐색
dfs(k, 0, 1)
print(ans)

❇️오늘의 회고

  - N의 범위가 크지 않아 플로이드 워셜을 충분히 이용할 수 있었다!

  - 입력받은 거리 테이블에 플로이드 워셜로 최단거리를 바로 덮어쓰기 하는 것에 주의하자!

  - 내일 11시, 문제를 풀기 전에 위 문제를 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂