[BOJ] [Python] 10971 : 외판원 순회 2

예제 입력 1

 

문제의 예제 입력을 표로 작성해보았다.

 

 

주의할 점

 

1. 모든 도시를 경유한다.

2. [i][j]가 0일 경우 갈 수 없는 길이다.

3. 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)

 

 

고민했던 점

 

1. 어디서 출발해야 할까?

2. 어떻게 최단 거리로 모두 경유할까?

 

모든 도시를 경유해야 하는 문제 때문에, 다익스트라 알고리즘을 사용하지 않았다.

백트래킹으로 해결해 보자.

 

 

n = int(input())

li = []

li_idx = []
dp = [0] * n

result = 1e9

for _ in range(n):
    li.append(list(map(int, input().split())))


def back(cnt):
    global result

    if cnt == n:
        tmp = 0

        if li[li_idx[-1]][li_idx[0]] == 0:  # 갈 수 없는 길
            return

        for idx in range(n - 1):
            i = li_idx[idx]
            j = li_idx[idx + 1]

            if li[i][j] == 0:  # 갈 수 없는 길
                return

            tmp += li[i][j]

        tmp += li[li_idx[-1]][li_idx[0]]
        result = min(result, tmp)

        return

    for i in range(n):
        if dp[i] == 0:
            li_idx.append(i)
            dp[i] = 1

            back(cnt + 1)

            dp[li_idx[-1]] = 0
            li_idx.pop()


back(0)
print(result)

 

 

먼저, 이동 경로를 생각해보자.

 

백트래킹을 이용해서, 갈 수 없는 길(비용이 0인 곳)을 포함한 모든 이동 경로를 찾아야 한다.

(다만, dp를 이용해서 한 번 갔던 길은 가지 않는다.)

 

만약에 (0, 1)이라면 (0에서 1로 이동했다면),

다음에는 (1, 0을 제외한 index)여야 한다.

 

이동 경로가, 예를 들어 [0, 1, 2, 3] 이렇게 나올 수 있도록 했다.

(0, 1) -> (1, 2) -> (2, 3) -> (3, 0)

 

 

다음은 이 이동 경로를 가지고 총 비용을 찾아보자.

 

갈 수 없는 길을 포함한 이동 경로는 쓸모없다.

갈 수 있는 길로만 이루어진 이동 경로만 생각할 것이고,

이 길들의 비용들을 모두 더해준다.

 

해당 이동 경로에 해당하는 총 비용이 나왔으면 일단 저장한다.

 

 

마지막에 구해진 총 비용들 중에서 최솟값이 정답이다.

 

(시간초과 때문에 pypy로 제출하고 통과했다.)