BOJ 10971

Input

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10)

다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

import sys
sys.setrecursionlimit(10 ** 6)

N = int(sys.stdin.readline())
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

DFS

• 시작점을 모두 다르게 해서 탐색해야 하므로 for 문으로 dfs 실행

  for now in range(N):
    dfs(now, now, 0, [now])

• 시작점이 아니며, visited == False 이며, cost != 0 인 경우 dfs 실행

  • 실행 시 visited True 체크 했다가 모든 확인을 마치고 return 후 dfs를 빠져나오면 해당 노드를 False 체크하여 다음 경우의 수를 검사하도록 함

  for idx in range(N):
    if cost[next][idx] != 0 and idx not in visited:
      visited.append(idx)
      dfs(start, idx, total + cost[next][idx], visited)
      visited.pop()

• visited 의 길이가 N 인 경우 모든 노드를 방문한 것이므로 start 지점으로 돌아와야 한다. 이 때 cost != 0 이라면 min 을 업데이트한다.

  if len(visited) == N:
    if cost[next][start] != 0:
      minCost = min(minCost, total + cost[next][start])
    return

• 가장 중요한 것은: 현재 total 값이 이미 minCost 를 초과한 경우, return 을 통해 빠져나와야 시간 초과가 뜨지 않는다!!!

Output

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

  if len(visited) == N:
    if cost[next][start] != 0:
      minCost = min(minCost, total + cost[next][start])
    return

sys.stdout.write(str(minCost))