외판원 순회2

입력

첫째 줄에 도시의 수를 입력
둘째 줄부터 N+1번째 까지 N*N의 cost 맵을 입력

출력

모든 도시를 방문했을 때의 최소 cost 값

조건

• 현재 도시에서 다음 도시로 가는 비용이 0이 아니어야 한다.
• 모든 도시를 다 방문해야 한다.

풀이

• cost에 대한 map이 주어졌을 때 그것을 map으로 보지말고 i→j로 이동할 때의 cost 값으로 생각한다.
• N이 도시들의 개수이면 col을 도시라고 생각하고 row를 다음에 갈 도시라고 생각한다.

1. 시작 도시를 처음부터 N까지 반복문을 돌린다.

for i in range(N):
    visited = [False]*N
    dfs(i, i, N, 0, visited)

2. 종료 조건으로는 최소 cost 값을 구하는 것이기 때문에 cnt가 현재 최소값을 넘을 경우 + 모든 도시를 돌고 처음 도시로 돌아왔을 경우로 한다.
   다음 도시로 가는 경우는 방문하지 않은 도시여야하며 현재 도시에서 다음 도시로 가는 cost가 0보다 커야한다.

def dfs(start, cur, rm, cnt, visited):
    global _map, ans

    if cnt >= ans: return
    
    if start == cur and rm == 0:
        ans = min(ans, cnt)
        return
    
    for j in range(N):
        if j != cur and visited[j] == False and _map[cur][j] != 0:
                visited[j] = True
                dfs(start, j, rm-1, cnt+_map[cur][j], visited)
                visited[j] = False

전체코드

외판원 순회2