[SW Expert Academy] 5189. 전자카트

5189. 전자카트

---

문제)

 

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

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

각 구역을 이동할 때의 배터리 사용량은 표로 제공되며, 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

 

 

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

 

 

[입력]

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

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

 

 

[출력]

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

 

 

 

 

풀이)

 

def recur(cur, total):
    global ans
 
    # 첫 정답 갱신 이후 total이 ans를 넘어서면 가지치기
    if total > ans:
        return
 
    # 관리구역을 다 돌고, 사무실로 돌아왔을 때 
    if cur == 0 and sum(visited[1:]) == n - 1:
        ans = min(ans, total)
        return
    
    # 관리구역을 도는 경우의 수
    for i in range(n):
        if visited[i] or cur == i:
            continue
        visited[i] = 1
        recur(i, total + li[cur][i])
        visited[i] = 0
 
T = int(input())
for _ in range(T):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n)]
    visited = [False] * n
    ans = 1 << 20
    recur(0, 0)
    print(f"#{_ + 1} {ans}")
 

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.