[SWEW] 5189. 전자카트 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

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

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

 

< ❓ 생각 >

< 💻 코드 >

# idx : 방문 횟수, k : 현재 위치
def check(idx,s,k):
    global min_sum
    # 도착?
    if idx == N:
        # 되돌아오기
        s += arr[k][0]
        if min_sum > s:
            min_sum = s
        return
    # 최솟값을 구하는 것이니 이미 이전 최솟값보다 크면 계산 필요X
    if s > min_sum:
        return
    for i in range(1,N):
        if used[i] == 0: # 방문한 적 X
            used[i] = 1 # 방문표시
            check(idx+1,s+arr[k][i],i)
            used[i] = 0 # 되돌리기

# 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    N = int(input())
    # r->c 이동시 베터리 소모량 arr[r][c]
    arr = [list(map(int,input().split())) for _ in range(N)]

    min_sum = 10000000000
    # 방문 표시
    used = [0]*N
    used[0] = 1
    check(1,0,0)
    
    print(f'#{tc} {min_sum}')

< ❗ 느낀 점 >

5188. 최소합과 거의 비슷해서 금방 풀었다.

https://chaemi720.tistory.com/92

[SWEA] 5188. 최소합 - Python