TIL) 10971 외판원순회2

✨ dfs의 등장

💡 아이디어

• 이차원 배열을 이용해서 경로의 비용을 저장한다.
• visited를 이용해서 경로를 이미 지난 경우 체크해준다.
• dfs함수의 매개변수 origin을 이용해서 시작 점을 계속 가지고 간다.
• 지난 경로의 개수를 체크해주는 cnt를 이용해서 3개의 경로를 지난 후에는 처음 경로까지의 길이 있는지 확인해주고 있을 경우 총 비용을 구한다.
• cnt가 3이 아닌 경우에는 현재 경로 pos에서 다음 경로 i까지의 길이 있는지 확인하고 재귀함수를 통해 확인해준다.
• 재귀함수를 사용하고 나서는 빠져나왔을 때에는 방문처리 해 놓았던 것을 다시 초기화시켜줘야 다음번 순서에서 다시 사용할 수 있다.

N = int(input())

way = [0]*N
visited = [0]*N

for i in range(N):
    way[i] = list(map(int, input().split()))

ans = 1e9

# dfs함수 구현
def dfs(origin, pos, cnt, cost):
    # 마지막 지점에서 시작 지점으로 가는 카운트라면
    if cnt == N-1:
        # 마지막 지점에서 시작 지점으로 가는 길이 없으면 리턴
        if way[pos][origin] == 0:
            return
        else:
            # 마지막 지점에서 시작 지점으로 가는 비용을 총 비용에 더해주고
            cost += way[pos][origin]
            global ans
            # 기존에 저장해놓은 ans랑 현재 비용을 비교해서 최소값을 ans에 저장
            ans = min(ans, cost)
            return

    # 아직 마지막 지점이 아닐 때
    for i in range(N):
        # i 도시에 간적없고 현재 도시에서 i 도시로 가는 길이 있을 때
        if visited[i] == 0 and way[pos][i] > 0:
            # i 도시에 방문처리 해주고
            visited[i] = 1
            # 시작점 origin을 계속 저장해주고 현재 지점을 i로 이동, cnt 1 증가, 비용은 기존 cost에 현재위치에서 i로 가는 비용 추가
            dfs(origin, i, cnt+1, cost+way[pos][i])
            visited[i] = 0


for i in range(N):
    for j in range(N):
        if way[i][j] > 0 :
            visited[i] = 1
            visited[j] = 1
            dfs(i, j, 1, way[i][j])
            visited[i] = 0
            visited[j] = 0

print(ans)