최소 스패닝 트리 (7) 썸네일형 리스트형 백준 17490번 [일감호에 다리 놓기](C++) -yes6686- 티스토리 백준 문제 풀이: 17490 [일감호에 다리 놓기]문제 링크: https://www.acmicpc.net/problem/17490문제 설명:일감호에는 총 N개의 섬이 원형으로 배치되어 있습니다. 일부 섬 사이에는 이미 다리가 설치되어 있고, 다른 다리는 비용이 주어졌습니다. 주어진 예산 K 안에서 모든 섬을 연결하는 것이 가능한지 판단하는 문제입니다.즉, 최소 스패닝 트리를 구성하여 그 비용이 예산 K를 초과하지 않는지 확인하면 됩니다.문제 해결 코드#include #include #include using namespace std;// 간선을 저장할 벡터vector>> edges;int connected[1000001]; // 특정 섬 사이 다리가 이미 설치되어 있는지 체크int parent[10000.. 백준 1197번 [최소 스패닝 트리](C++) -yes6686- 티스토리 백준 문제 풀이: 1197 [최소 스패닝 트리]문제 링크: https://www.acmicpc.net/problem/1197문제 설명:가중치가 있는 무방향 그래프에서 모든 정점을 연결하는 부분 그래프 중 가중치의 합이 최소가 되는 그래프를 찾는 문제입니다. 이러한 그래프를 "최소 스패닝 트리(MST)"라고 합니다.문제 해결 코드#include #include #include using namespace std;// 간선을 저장하는 벡터vector>> edges;int parent[10001]; // 부모 노드 저장 배열// 부모 노드 찾기 (경로 압축)int getParent(int n) { if (parent[n] == n) return n; return parent[n] = getParen.. 백준 2887번 [행성 터널](C++) -yes6686- 티스토리 백준 문제 풀이: 2887 [행성 터널]문제 링크: https://www.acmicpc.net/problem/2887문제 설명:N개의 행성이 3차원 좌표에 위치하고 있으며, 특정 행성들 사이를 터널로 연결하려고 합니다. 터널의 비용은 두 행성 간의 거리로 정의됩니다. 모든 행성을 연결하면서 최소 비용으로 터널을 구성하려면 어떻게 해야 할까요?문제 해결 코드#include #include #include using namespace std;int parent[100001];struct st { int x, y, z; int num;};struct edge { int a, b; int dis;};edge Ed[300001];st St[100001];int GetParent(int x) .. 백준 1647번 [도시 분할 계획](C++) -yes6686- 티스토리 백준 문제 풀이: 1647 [도시 분할 계획]문제 링크: https://www.acmicpc.net/problem/1647문제 설명:도시를 두 개의 구역으로 분리하려고 합니다. 도시에는 집과 길이 있으며, 모든 길은 유지 비용이 있습니다. 길을 최소한으로 선택하여 모든 집들이 연결되도록 하고, 두 구역으로 나누었을 때의 최소 비용을 구하는 문제입니다. 단, 두 구역 사이에 길이 없어야 합니다.문제 해결 코드#include #include using namespace std;int parent[100001];// 부모 노드 찾기int GetParent(int x) { if (parent[x] == x) return x; return parent[x] = GetParent(parent[x].. 백준 2406번 [안정적인 네트워크](C++) -yes6686- 티스토리 백준 문제 풀이: 2406 [안정적인 네트워크]문제 링크: https://www.acmicpc.net/problem/2406문제 설명:주어진 컴퓨터 네트워크에서 안정적인 네트워크를 구성하기 위해 최소 비용으로 추가해야 할 연결들을 구하는 문제입니다. 초기 연결 상태가 주어지고, 각 컴퓨터 쌍의 연결 비용이 주어질 때, 추가로 연결해야 할 최소 비용과 연결 목록을 출력합니다.네트워크 안정성을 유지하기 위해 모든 컴퓨터가 하나의 네트워크로 연결되어야 합니다.문제 해결 코드#include #include #include using namespace std;int parent[1001]; // 각 노드의 부모를 저장하는 배열priority_queue>, vector>>, greater> pq;int findPa.. 백준 10021번 [Watering the Fields](C++) -yes6686- 티스토리 백준 문제 풀이: 10021 [Watering the Fields]문제 링크: https://www.acmicpc.net/problem/10021문제 설명:농장의 각 좌표에서 물을 대기 위해 필요한 간선의 비용과 조건을 고려하여 최소 스패닝 트리를 구성하는 문제입니다. 다음 조건이 적용됩니다:간선의 비용은 두 점 사이의 거리의 제곱으로 계산됩니다.간선의 비용은 주어진 최소 거리 c 이상이어야 합니다.모든 점이 연결될 수 없을 경우 -1을 출력합니다.문제 해결 코드#include #include #include #include using namespace std;int parent[2001]; // 부모 배열pair arr[2001]; // 좌표를 저장할 배열priority_queue>, vector>>,.. 백준 20010번 [악덕 영주 혜유](C++) -yes6686- 티스토리 백준 문제 풀이: 20010 [악덕 영주 혜유]문제 링크: https://www.acmicpc.net/problem/20010문제 설명:그래프의 최소 스패닝 트리(MST)를 구성하고, 이를 기반으로 다음 두 가지를 계산하는 문제입니다:최소 스패닝 트리를 구성하는 간선의 총 비용최소 스패닝 트리에서 두 점 사이의 최장 경로문제 해결 코드#include #include #include #include #define INF 1e9using namespace std;vector> adj[1001]; // MST를 저장할 인접 리스트priority_queue>, vector>>, greater> pq; // 간선 정보를 저장할 우선순위 큐int parent[1001]; // 부모를 저장하는 배열in.. 이전 1 다음
