10971: 외판원 순회2

프로그래머는 자신의 일을 효율적으로 컴퓨터에 떠넘겨야 한다.
이를 확실히 깨달은 문제. '외판원 순회2'다.

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

def dfs(start, now, value, cnt):
    global ans
    if cnt == N:
        if a[now][start]:
            value += a[now][start]
            ans = min(ans, value)
        return

    if value > ans:
        return

    for i in range(N):
        if not visited[i] and a[now][i]:
            visited[i] = 1
            dfs(start, i, value + a[now][i], cnt + 1)
            visited[i] = 0


ans = sys.maxsize
visited = [0] * N
for i in range(N):
    visited[i] = 1
    dfs(i, i, 0, 1)
    visited[i] = 0
print(ans)

처음에도 재귀로 구현하긴 했으나, 이차원 배열을 선언하여 재귀함수 내에서 최솟값을 찾는 형태였다. 따라서 복잡도도 높았고 튀어나오는 반례들도 재귀함수 내에서 처리했었다.
하지만 dfs방식으로 한 지점에 갔을 때, 바로 가능한 다음 지점을 탐색하며 비용의 최솟값을 비교해주는 형태가 되니 코드도 단순해지고 효율적으로 되었다.

visited를 선언하여 방문했던 지점을 기억하고, value를 더해주며 총합의 최솟값을 출력했다.
python에서 이차 배열을 처음 선언해본 문제이기도 하다.

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