[백준 10971] 외판원순회 2

10971번

문제

처음에는 그리디인가?해서 각 길마다 최선의 경로를 선택하면 될까? 했지만 그게 아니었다!

그래서 일단 어느 경로들이 나올 수 있는지 주어진 예제를 이용해 다 계산해 보았다.

노란색으로 표시한 경로가 가장 최소 비용을 가지는 경로였다.

한 도시에서 다른 도시로 이동할 때 어떠한 기준(ex. 그리디)을 가지고 다음 도시를 선택하는 것이 아니라 도시 전체를 도는데 드는 비용을 모두 고려하기 때문에 완전탐색이 필요하다고 생각되었다.

그리고 도시의 수(N) 역시 $2<=N<=10$

그럼 어떻게 완전 탐색을 할까!?

순회하는 경로이기 때문에 어느 도시에서 시작하든 처음 시작한 도시로 돌아오게 된다.

즉, 시작하는 도시는 어디로 정하든 상관 없으니 A 도시로 고정하였다.

그리고 시작하는 도시를 정하니 탐색을 해야할 부분이 다음의 파란색 네모로 줄어든 것을 알 수 있었다.

파란색 네모는 A도시를 제외한 나머지 도시들의 순열로 구성된 것을 보고 dfs를 이용한 순열 코드를 작성하여 탐색을 진행했다!

city=int(input())
matrix=[[0]*city for _ in range(city)]
visit=[]
res = 0
minimum = 10000001

def combination(now, depth) :
  global res,minimum
  if depth == (city - 1) :
#return은 연결 성분이 0일때 예외처리를 한 부분
    if matrix[0][visit[0]] == 0 : return
    res = matrix[0][visit[0]]
    for i in range(len(visit)-1) :
      if matrix[visit[i]][visit[i+1]] == 0 : return
      res = res + matrix[visit[i]][visit[i+1]]
    if matrix[visit[-1]][0] == 0 : return
    res = res + matrix[visit[-1]][0]

    if minimum > res :
      minimum = res

  for j in range(1,city) :
    if j not in visit :
      visit.append(j)
      combination(j,depth+1)
      visit.pop()


#2차원 배열 입력받기
for i in range(city) :
  new=input().split()
  for j in range(city) :
    matrix[i][j] = int(new[j])

#조합 순회
for i in range(1,city) :
  visit.append(i)
  combination(i,1)
  visit.pop()

print(minimum)