악곱 == 악성곱슬

백트래킹

---

이 문제는 외판원 순회 문제로, 백트래킹을 사용하여 구현할 수 있다.

모든 지점을 지나서 자기 자신으로 돌아오는 경로중 최단 경로를 구해야 한다. 이 문제는 노드의 수가 최대 10개이므로 그냥 완전 탐색(순열, 조합)으로 풀 수 있는 유형이다. 따라서 일반 DFS(Backtrack)을 통해서 방문한 노드를 하나씩 마킹하며 순회하면 된다.

비트마스크 및 DP를 이용하는 문제는 다른 인풋이 더 큰 난이도로 리뷰하도록 하겠음.

구현

---

import sys

def backtrack(depth, n, cost, start, cur, visited):
    global answer
    if cost >= answer:
        return
    if depth == n:
        if graph[cur][start] == 0:
            return
        answer = min(cost + graph[cur][start], answer)
        return
    for i in range(n):
        if visited[i] or graph[cur][i] == 0:
            continue
        visited[i] = True
        backtrack(depth+1, n, cost + graph[cur][i], start, i, visited)
        visited[i] = False
    return

def solution(n):
    visited = [False] * n
    for i in range(n):
        visited[i] = True
        backtrack(1, n, 0, i, i, visited)
        visited[i] = False

if __name__ == "__main__":
    answer = int(1e9)
    N = int(sys.stdin.readline().rstrip())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
    solution(N)
    print(answer)