[백준] Python - 10971.외판원순회2

생각

각 도시마다 간선별 비용이 다를수있으므로 도시별로 방문 순서가 다르면 비용이 다릅니다. 따라서 이를 순서의 다름이 의미의 다름을 뜻하는 순열로 생각하고 문제를 풀었습니다.

1. i->j 로 가는 도시의 비용을 저장하는 2차원 배열을 만들어 입력을 통해 모두 저장해줍니다.
2. 방문체크를 위해 N개의 도시의 방문여부를 False로초기화시켜줍니다.
3. 도시의 방문 순서를 만들어주는 dfs 함수입니다.
   1. 다음노드를 방문할수있는 상태(0보다 큰값을 가지는 노드)이고 방문하지 않았다면 방문 체크를 True로 만들어주고 다음 단계로 들어갑니다. 이때 비용은 현재 비용에서 다음방문 비용을 더해줘야합니다.
   2. 현재노드에서 뒤로 나열할수있는 모든 도시를 정했으므로 다음 노드의 순열을 만들기위해 방문 체크를 False로 갱신합니다.
   3. 모든 도시를 다 방문하였고 처음 도시로 돌아왔으면 글로벌 변수인 answer에 저장된 비용과 최소값을 비교한다음 최소값을 answer에 넣어주고 종료합니다.

Python 코드

#가장 적은 비용을 들이는 여행경로 -> 최소비용 출력
import sys

def dfs(start, now, cost):
    global answer
    #모든 도시를 들렀고 다시 처음으로 돌아오면 비용 갱신하고 리턴
    if start == now and all(visited):
        answer = min(answer, cost)
        return
    else:
        for next_node in range(N):
            if map[now][next_node] > 0 and not visited[next_node]:
                visited[next_node] = True
                dfs(start, next_node, cost + map[now][next_node])
                visited[next_node] = False


if __name__ == "__main__":
    N = int(input())
    # map[i][j] : i -> j 비용
    map = [list(map(int, input().split())) for _ in range(N)]
    visited = [False] * N #방문여부
    answer = sys.maxsize 
    dfs(0, 0, 0)
    print(answer)