[Python] 여행하는 외판원 문제
Algorithm

[Python] 여행하는 외판원 문제

일시불

여행하는 외판원

최소 비용의 edge를 연결하는 방식으로 최소신장트리를 구현한다.

해결 코드

sys모듈을 사용할 수 있으면 INF를 사용해서 연결행렬 구현이 가능하기 때문에 좀 더 깔끔하게 코드를 쓸 수 있지만.. 간혹 코딩테스트 IDE에서 sys모듈 import가 안되는 경우가 있다고 해서 해당 모듈 없이 구현해봤다.

코드에 좀 더 개선의 여지가 있는 것 같은데 어떻게 해야할 지 영 모르겠다..

# sys 모듈 사용할 수 없는 경우
def travelingsalesman(numV, nodes):
    edges = [[0] * (numV + 1) for _ in range(numV + 1)]
    for node in nodes:
        edges[node[0]][node[1]] = node[2]
        edges[node[1]][node[0]] = node[2]

    # find minimum distance
    visit = [0] * (numV + 1)
    memo = [0] * (numV + 1)
    curr = 7
    visit[curr] = 1

    dist = 0
    while sum(visit) < numV:
        temp = []
        # Find unvisited nodes
        for k in [i for i, j in enumerate(visit) if j == 0 and i > 0]:
            # Find min. dist. from unvisited nodes
            weight = [[k, b] for a, b in enumerate(edges[k]) if b > 0 and visit[a] == 1]
            if weight:
                temp.append(min(weight, key=lambda x: x[1]))

        if temp:
            cand = min(temp, key=lambda x: x[1])
            dist += cand[1]
            visit[cand[0]] = 1

    return dist


nodes = [
    [1, 7, 12],
    [4, 7, 13],
    [1, 5, 17],
    [3, 5, 20],
    [2, 4, 24],
    [1, 4, 28],
    [3, 6, 37],
    [5, 6, 45],
    [2, 5, 62],
    [1, 2, 67],
    [5, 7, 73],
]
numV = 7
print(travelingsalesman(numV, nodes))