[파이썬] SWEA 1247 : 최적 경로 (D5)

[파이썬] SWEA 1247 : 최적 경로 (D5)

• SWEA 1247 : 최적 경로

---

풀이

방향성 생각

• 완탐 or 비트마스킹 다익
• 맵 크기가 충분히 작아서 이 상태에서도 비트 다익을 돌려도 된다.
• 하지만, 노드 수가 적고 간선 코스트를 구하는게 쉬워서 2차원에서 1차원으로 압축시켜주기.
• 간선 코스트가 다르니까 다익스트라 사용.
• 방문 유무를 비트마스킹으로 관리

 

전체코드

import heapq as hq

INF = float('inf')

TC = int(input())
for tc in range(1,TC+1):

    N = int(input())
    infos = list(map(int,input().split()))

    done = (1<<N)-1

    # node 0 : start, 1 : end. 2 ~ : mission
    # G[i] = (j,cost) (i->j : cost)
    G = [[] for _ in range(N+2)]
    for i in range(N+2):
        x,y = infos[2*i:2*i+2]
        for j in range(N+2):
            if i!=j:
                nx,ny = infos[2*j:2*j+2]
                G[i].append((j,abs(x-nx)+abs(y-ny)))

    # V[state][node]
    V = [[INF]*(N+2) for _ in range(1<<N)]
    V[0][0] = 0
    heap = [(0,0,0)] # time, node, state
    while heap:

        t,x,s = hq.heappop(heap)
        # print(t,x,s)
        # finish
        if x == 1 and s == done:
            print(f"#{tc} {t}")
            break

        # search
        for nx,cost in G[x]:
            nt = t+cost

            # visit customer
            ns = s
            if nx > 1:
                ns = s | (1<<(nx-2))

            if nt < V[ns][nx]:
                V[ns][nx] = nt
                hq.heappush(heap,(nt,nx,ns))

코멘트

• .