[백준-파이썬] 10971: 외판원 순회 2

문제 보러 가기!

아이디어 💕

도시 간 이동하는 데 드는 비용이 행렬에 저장되어 있다. 모든 도시를 순회하고, 다시 원래 출발점으로 돌아와야 한다. 이때 가장 적은 비용이 들 때 얼마나 드는지 출력하는 문제이다.
도시가 최대 10개니까 브루트포스하게 다 봐도 될 거 같다고 생각했다.
일단은 모든 도시에서 출발해보았다. 방문했던 곳은 못 가니까 방문 체크도 하고 ! 다만 원래 출발점으로는 다시 돌아와야 하니까 그 부분은 다르게 처리했다.

처음 코드(파이썬-시간초과, 파이파이- 3140ms) 😂

import sys

input = sys.stdin.readline

N = int(input())

cost_matrix = list(list(map(int, input().split())) for _ in range(N))


def dfs(curr_city, total_cost):
    global smallest_cost
    if curr_city == k and visited[k] == 2:  # 다시 돌아왔으면
        for v in visited:
            if v == 0:  # 방문 안 한 곳 있으면
                return
        smallest_cost = min(smallest_cost, total_cost)
        return

    for i in range(N):
        next_city_cost = cost_matrix[curr_city][i]
        if next_city_cost != 0 and i == k:  # 출발지로 가는 경우
            visited[i] += 1
            dfs(i, total_cost + next_city_cost)
            visited[i] -= 1

        if next_city_cost != 0 and visited[i] == 0:  # 갈 수 있고, 방문하지 않은 곳이라면
            visited[i] += 1
            dfs(i, total_cost + next_city_cost)
            visited[i] -= 1


smallest_cost = 1000000 * 10
for k in range(N):
    visited = [0] * N  # 도시 방문 체크
    # 모든 도시에서 시작해보기
    visited[k] = 1
    dfs(k, 0)  # 출발 도시, 비용

print(smallest_cost)

두번째 코드(파이썬으로도 통과) 😎

def dfs(curr_city, total_cost):
    global smallest_cost

    if total_cost > smallest_cost: # 이미 최솟값 아니라면
        return

이 부분을 추가했다! 이미 최솟값이 아닌 게 밝혀졌으면 바로 리턴하는 걸로!
그랬더니 파이썬으로도 통과할 수 있었고, 시간이 많이 단축되었다 :)