백준 - 10971

문제 설명

N개의 마을이 있고, 각 마을 사이에는 길이 있으며 2차원 배열로써 각 길에 대한 비용이 주어진다.

마을 사이에 길이 없는 경우는 0으로 주어지며, 어느 한 마을에서 시작해서 모든 마을을 전부 돈 후, 시작한 마을로 돌아왔을 때 비용이 최소인 경우를 출력하는 문제다.

접근 방식

• n개의 마을이 주어지므로, 각 마을에서 출발했을 때의 모든 경우를 살피며 경로가 최소가 되는 경우를 출력한다.
  
  
• 모든 경우를 고려하려면 시간이 부족할 수 있기 때문에, 마을을 도는 와중에 현재까지 가장 작은 비용으로 1바퀴를 돈 경우보다 비용이 크게 된 경우에는 과감히 버리고, 다른 경우를 선택하여 탐색을 수행한다.
  
  
• sys.maxsize는 9,223,372,036,854,775,808 를 반환한다.
  
  
• 시작 위치를 기억한 상태에서 가능한 경우를 골라야 하므로, 함수를 수행함에 있어 파라미터로 넘겨줘야 한다.

테스트 데이터에 나와있는 35의 도출과정을 보면 다음과 같다.

작성한 코드

import sys
input = sys.stdin.readline

n = int(input())
price_list = []		# 길 비용을 저장
ans = sys.maxsize	# 파이썬 최대 정수 할당
visit = [0 for _ in range(n)] # 방문 여부 확인

for i in range(n):
    price_list.append(list(map(int, input().split())))

def back(start, now, value, count):
    global ans	# 전역변수 활용

    if count == n:	# 1바퀴 다 돌은 경우에
        if price_list[now][start]:	# 시작점으로 돌아가는길이 있는 경우에만
            value += price_list[now][start]
            if ans > value: 		# 최소값 갱신
                ans = value
        return						# 없는 경우 리턴
    
    if value > ans:         # 이미 경로 크기가 커져버린 경우
        return
    
    for i in range(n):		
        if not visit[i] and price_list[now][i]:	# 방문도 안했고, 0이 아닌 경우에
            visit[i] = 1						# 방문 처리 
            back(start, i, value + price_list[now][i], count+1) # 재귀
            visit[i] = 0						# 방문 처리 초기화

for i in range(n):
    visit[i] = 1
    back(i, i, 0, 1)							
    visit[i] = 0

print(ans)