반응형 프림3 [알고리즘] c++ cpp 네트워크 연결 포인트 1. mst 를 잘 이해할 수 있는가를 묻는 문제 (mst 는 크루스칼 알고리즘, 프림 알고리즘 등이 있다. ) 크루스칼 알고리즘이 빠르긴하다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 프림 알고리즘 #include #include #include #include using namespace std; int n, m; bool visited[1001]; vector map[1001]; //가중치, 목적지 priority_queue pq; //가중치기준 최소힙 int prim() { int ans = 0; pq.push({0, 1}); while (!pq.empty()) { int cost, x; tie(cost, x) = pq.top(); pq.pop(); if (visited[x.. 2020. 10. 23. [알고리즘] c++ cpp 지형 이동 포인트 1. bfs, 프림 알고리즘을 섞는다. bfs 는 구역의 이름을 짓기위하여 실행을 한다 프림은 mst 를 구하기 위하여 실행을 한다. 2. 아직 이 문제는 어렵다. 억지로 풀기는 하였다 그래도 중요하다고 생각을 하는 부분은 중간에 있는 calc 함수라고 생각을 한다. calc 를 통해서 맵을 돌면서 인접 섹션이 다른 것들을 노드로 하고 이를 도는 mst 를 만드는 생각이 중요한 것 같다. 프림은 아무리 여러개가 연결이 되어 있어도 결국은 하나의 경로를 택하기 때문에 따로 처리는 상관이 없다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; int section[301][301]; int visited[301][301];.. 2020. 10. 23. [알고리즘] 최단 경로(다익스트라), MST (프림) 포인트 1. 다익스트라 알고리즘과 프림 알고리즘은 거의 차이가 없다. 다익스트라는 값을 계속해서 더해서 나간다고 생각을 하면 된다. 다익스트라 #include #include #include using namespace std; vector map[101]; vector dijkstra(int start, int goal) { vector dist (goal, 9876554321); dist[start]=0; priority_queue pq; pq.push ({ 0, start }); while(!pq.empty()) { int x, cost; tie (cost, x)=pq.top (); pq.pop (); if (dist[x] < cost) continue; for(auto ele : map[x]) {.. 2020. 10. 22. 이전 1 다음 반응형