[백준 2024/09/07] 10971번 외판원 순회 2

1. 문제

https://www.acmicpc.net/problem/10971

 

2. 접근 방법

예를 들어, 3개의 도시가 있다고 가정하자.

3개의 도시는 0번, 1번, 2번 이라는 이름이 있다고 할 것이다.

 

그렇다면 도시를 방문하는 순서의 경우의 수는 몇이 될 것인가? 3! 이다.

 

0 - 1 - 2 - 0

0 - 2 - 1 - 0

 

1 - 0 - 2 - 1

1 - 2 - 0 - 1

 

2 - 0 - 1 - 2

2 - 1 - 0 -2

 

이렇게 될 것이다.

 

반면, 다음과 같은 경우는 동일한 경우에 해당된다.

어떤 도시로부터 시작하냐의 차이일 뿐, 같은 cost를 지불하게 된다.

 

따라서, 이런 이동 경로의 경우의 수를 판단해서, cost 들을 계산해 주고, 최솟값을 반환하면 될 것이다.

 

def make_possibilities(curr, not_visited):
    if not not_visited:
        curr.append(curr[0])
        routes.append(curr)
        return

    length = len(not_visited)

    for i in range(length):
        make_possibilities(curr + [not_visited[i]], not_visited[:i] + not_visited[i + 1:])

주된 함수는 위와 같다.

curr로 [0]

not_visited로 [1, 2] 를 제공해 주게 될 것이다.

 

curr로 0을 제공해 주는 것은 시작점을 지정해 준 것과 같다.

이렇게 지정해 준 이유는, 위에서 사진에서 언급한 이유이다. 따라서, 시작점을 0으로 잡고 모든 경우의 수를 탐색하기 시작할 것이다.

이후 방문하지 않은 도시들에 대해서 for 문을 돌면서, curr에 하나씩 추가해 주게 되는 것이다.

curr 보단, visited라고 명명하는 것이 더 맞았을지도 모르겠다.

 

이후 not_visited가 비게 된다면, 이제 방문할 곳이 없으므로 첫 도시로 돌아가 준다.

 

[[0, 1, 2, 3, 0], [0, 1, 3, 2, 0], [0, 2, 1, 3, 0], [0, 2, 3, 1, 0], [0, 3, 1, 2, 0], [0, 3, 2, 1, 0]]

 

모든 경로의 경우의 수를 가지게 될 것이다.

 

따라서, 0번 도시에서 1번 도시로 이동하는 cost, 1번 도시에서 2번 도시로 이동하는 cost를 계산하여 준다 .... 그렇게 모든 경우의 수를 계산해 주고, 가장 작은 최솟값을 반환하면 된다.

 

하지만, 유의해 주어야 할 부분이 있다.

cost가 0일 때이다.

cost가 0이면, 이동할 수 없기 때문에 계산을 멈춰야 한다.

나의 경우엔, cost가 0이라면, cost += 1000000을 해주어, 최솟값이 될 수 없도록 하였다.

 

3. 코드

routes = []


def make_array(n):
    big_arr = []
    for i in range(n):
        arr = list(map(int, input().split()))
        big_arr.append(arr)

    return big_arr


def make_possibilities(curr, not_visited):
    if not not_visited:
        curr.append(curr[0])
        routes.append(curr)
        return

    length = len(not_visited)

    for i in range(length):
        make_possibilities(curr + [not_visited[i]], not_visited[:i] + not_visited[i + 1:])
        


def find_min_cost(arr):
    costs = []
    for route in routes:
        cost = 0
        for i in range(len(route) - 1):
            if arr[route[i]][route[i + 1]] == 0:
                cost += 1000000
            cost += arr[route[i]][route[i + 1]]

        costs.append(cost)

    return min(costs)


if __name__ == "__main__":
    n = int(input())
    arr = make_array(n)
    make_possibilities([0], [i for i in range(1, n, 1)])
    print(find_min_cost(arr))