[파이썬 | SW Expert Academy] 전자카트

[문제]

 

골프장 관리를 위해 전기 카트로 사무실에서 출발해 각 관리구역을 돌고 다시 사무실로 돌아와야 한다.

사무실에서 출발해 각 구역을 한 번씩만 방문하고 사무실로 돌아올 때의 최소 배터리 사용량을 구하시오.

각 구역을 이동할 때의 배터리 사용량은 표로 제공되며, 1번은 사무실을, 2번부터 N번은 관리구역 번호이다.

두 구역 사이도 갈 때와 올 때의 경사나 통행로가 다를 수 있으므로 배터리 소비량은 다를 수 있다.

N이 3인 경우 가능한 경로는 1-2-3-1, 1-3-2-1이며 각각의 배터리 소비량은 다음과 같이 계산할 수 있다.

e[1][2]+e[2][3]+e[3][1] = 18+55+18 = 91

e[1][3]+e[3][2]+e[2][1] = 34+7+48 = 89

 

e	1	2	3	도착
1	0	18	34
2	48	0	55
3	18	7	0
출발

이 경우 최소 소비량은 89가 된다.


[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 100이하의 자연수가 주어진다. 3<=N<=10

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

[풀이]

 

무조건 처음 시작은 1번이고, 마지막도 1번이다.

따라서 1번 사이 2, 3, 4, ... , N번까지 다양한 경로가 존재한다.

그런데 N의 제한이 최대 10이므로, 1번을 제외한 9개까지의 순열을 고려하면, 최대 9! = 약 36만 밖에 안된다

 

따라서 모든 순열의 케이스를 구해서 각 케이스마다 O(1)의 시간복잡도로 답을 게산해서 최소값을 구하면된다.

 

따라서 이 문제에서 가장 어려운것은 C++ STL의 next_permutation을 구현하는 것이다.

 

그 후에는 1부터 N-1까지(index로 생각)의 list의 permutation을 돌려가면서 L[i-1]와 L[i]사이의 필요값을 더해나가면 된다.

 

그 후 모든 케이스에서의 최소값을 구하면 된다.

 

 

 

 

 

def next_permutation(a):
    for i in reversed(range(len(a) - 1)):
        if a[i] < a[i + 1]:
            break  # found
    else:  # no break: not found
        return False  # no next permutation
 
    # Find the largest index j greater than i such that a[i] < a[j]
    j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])
 
    # Swap the value of a[i] with that of a[j]
    a[i], a[j] = a[j], a[i]
 
    # Reverse sequence from a[i + 1] up to and including the final element a[n]
    a[i + 1:] = reversed(a[i + 1:])
    return True
 
def solve(L):
    length = len(L)
    ret = maps[0][L[0]]
    for i in range(1, length):
        ret += maps[L[i-1]][L[i]]
    ret += maps[L[length-1]][0]
 
    return ret
 
 
T = int(input())
 
for t in range(1, T+1):
    N = int(input())
    maps = []
    for _ in range(N):
        maps.append(list(map(int, input().split())))
    L = list(range(1, N))
    ans = solve(L)
    while next_permutation(L):
        temp = solve(L)
        if ans > temp:
            ans = temp
 
    print('#%d %d' %(t, ans))