[Python/BOJ] 17182. 우주 탐사선

https://www.acmicpc.net/problem/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)

출력

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

풀이

Code

import sys
input = sys.stdin.readline

ans = int(1e9)
def solution(n, k, graph) :
    # 1. 모든 행성 탐사 시간 체크 함수 정의
    def check() :
        # 1-1. 출력 변수 정의
        time = 0
        # 1-2.
        for i in range(n-1) :
            # 행성 이동 시간 더하기
            a, b = route[i], route[i+1]
            time += graph[a][b]
        # 1-3. 결과 리턴
        return time
    # 2. 백트래킹 함수 정의
    def backtracking(cnt) :
        global ans
        # 2-1. 종료 조건 설정
        if cnt == n :
            # 최소 거리 업데이트
            ans = min(ans, check())
            return
        # 2-2.
        for i in range(n) :
            # 2-2-1. 이미 리스트에 있는 경우(방문 처리가 되어 있는 경우) 건너뛰기
            if visited[i] : continue
            # 2-2-2. 행성 경로 리스트에 행성 번호 삽입, 방문 처리
            route.append(i)
            visited[i] = True
            # 2-2-3. 백트래킹 실행
            backtracking(cnt + 1)
            # 2-2-4. 행성 경로 리스트에 행성 번호 제거, 방문 해제
            route.pop()
            visited[i] = False

    # 3. 플로이드-워셜을 통해 행성 간 최소 시간 재정의
    for z in range(n) :
        for a in range(n) :
            for b in range(n) :
                if a != b :
                    graph[a][b] = min(graph[a][b], graph[a][z] + graph[z][b])
    # 4. 행성 이동 경로 리스트 생성
    route = [k]
    # 5. 행성 방문 여부 리스트 생성 후 시작 행성 방문 처리
    visited = [False for _ in range(n)]
    visited[k] = True
    # 6. 백트래킹 실행
    backtracking(1)
    # 7. 결과 출력
    print(ans)

if __name__ == "__main__":
    n, k = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    solution(n, k, graph)