🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 9

2098번: 외판원 순회

Traveling Salesman problem (TSP) 외판원 순회 문제

- 한붓그리기

- 다시 처음 노드로 돌아올 수 있어야 함

- 최솟값

---

으엥 이게 디피문제인가 최소 신장 트리 아닌가??

.

.

.

아 이런 멍청한놈,,

mst는 사이클만 안 생기면 통과다

그리고 외판원은 몸이 한 개다 한붓그리기

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())
qp = PriorityQueue() # 에지 정보 저장 큐 (에지리스트)

parent = [0] * (N) # 사이클확인(중복노드확인)용 유니온파인드 부모리스트
for i in range(N) :
    parent[i] = i

# 가중치 행렬 받기
mstLists = []
for i in range(N): 
    mstList = list(map(int,sys.stdin.readline().split()))
    mstLists.append(mstList)

# 우선순위 큐 넣기
for i in range(N): 
    for j in range(N): 
        if mstLists[i][j] != 0:
            qp.put((mstLists[i][j],i,j)) # 가중치 오름차순 정렬

def find(a):
    if a == parent[a] :
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
def union(a,b):
    A = find(a)
    B = find(b)
    parent[A] = B

useEdge = 0
result = 0

while useEdge < N-1 : # 크루스칼 알고리즘
    w,s,e = qp.get()
    if find(s) != find(e):  # 연결 시 사이클이 생기지 않으면 
        union(s,e)
        result += w
        useEdge += 1

print(result)

ㅠ 크루스칼 다 짰는데

---

사실

오랜만에 복습한거다

이제 진짜 시작해볼까

.

.

.

안봐도결과를아는쓰레기코드를깎아낸나

DP 하라니까 

브루트DFS시전

import sys

N = int(sys.stdin.readline())

# 가중치 행렬 받기
mstLists = []
for i in range(N): 
    mstList = list(map(int,sys.stdin.readline().split()))
    mstLists.append(mstList)

# 가중치인접리스트 변환
nearList = [[] for _ in range(N)] 
for i in range(N):
    for j in range(N):
        if mstLists[i][j] != 0:
            nearList[i].append((j,mstLists[i][j]))

# DFS
visited = [[False]]*(N)
result = []

def DFS(tar,v,rere):
    visited[v] = True 
    if False not in visited:
        for j,k in nearList[v]:
            if j == tar:
                rere += k
                result.append(rere)
                return
    
    for j,k in nearList[v] : 
        if not visited[j]:
            rere += k
            DFS(tar,j,rere)

            visited[j] = False
            rere -= k

for i in range(N):
    visited = [False]*(N)
    DFS(i,i,0)

print(min(result))

그래도 예의상 한번 내기

오 이건 예상 못했다

웬 인덴테이션에러..?

아하 그래그래 알고있었단다

---

사실 외판원 2 문제를 해결하기 위한 큰그림이었다

 

외판원 순회 : (2 ≤ N ≤ 16)  / 1초 - 연산 1억

외판원 순회 2: (2 ≤ N ≤ 10)  / 2초 - 연산 2억

 

시간복잡도  O(N!) 

 

 

이기 때문에 DP와 비트마스킹을 이용해야 한다.

.

.

.

하기싫다

비트마스킹!

비트마스킹안해봤다고

🧚‍♂️알고리즘🧚‍♂️ - 비트마스킹

이제 안다

---

준비는 다 되었지만..

내가 너무 지치고 배고프기 때문에 생각할 힘이 부족하여 

[python] 백준 2098 :: 외판원 순회 (DP, 비트마스킹)

굿

 

아~ 난 가짜골드야~