[BOJ] 외판원 순회 2

---

코드

from sys import stdin, maxsize
input = stdin.readline

def dfs(now, cost, cnt):    # 현재방문중인 도시, 현재까지의 총 비용, 방문한 도시 수
    global ans
    
    if cnt == N:
        if w[now][0]:    # 시작도시로 돌아가는 길이 있는 경우
            cost += w[now][0]    # 돌아가는 비용을 합산
            if cost < ans:        # 최소비용 갱신
                ans = cost
        return

    for i in range(N):
        # 방문하지 않은 도시 중 현재 도시에서 갈 수 있는 도시 방문
        if not visited[i] and w[now][i]:
            # 백트래킹 (dfs 수행후 방문여부 초기화)
            visited[i] = 1
            dfs(i, cost + w[now][i], cnt + 1)
            visited[i] = 0
    
    
# input
N = int(input())
w = [list(map(int, input().split())) for _ in range(N)]

# ans
visited = [0]*N    # 방문여부
visited[0] = 1
ans = maxsize
dfs(0,0,1)
print(ans)

결과

풀이 방법

• 현재 도시로부터 방문 가능한 도시들을 DFS로 방문하며 비용을 계산하고 최소비용을 찾는 문제이다.
• 모든 도시를 방문한 경우(cnt == N) 시작 도시로 돌아갈 수 있는지 확인하고 가능하다면 시작도시로 돌아가는 비용을 추가한 후 최소비용이라면 갱신한다.
• 도시를 시작 도시를 제외하고 여러 가지 순서로 방문하기 때문에 현재 도시에서 다른 도시를 DFS로 방문한 이후(DFS return문 수행 후)에는 방문한 도시를 미방문 처리해야한다 (백트래킹)

---