[C++/백준] 1647 도시분할계획

1647번: 도시 분할 계획

 

[문제]

 

-풀이 시 고려한 조건-

1. 마을 내 모든 집들은 임의의 경로로 이어져 있어야 한다. (간선은 모두 양방향)
2. 가장 적은 유지비가 들어야 한다.
3. 최소 유지비를 제외한 모든 길을 제외할 수 있다. 
4. N <= 100,000,  M<= 1,000,000

 

 

[풀이 과정]

 

처음에 문제를 봤을 때 "최소 유지 비용" 이라는 부분만 집중해서 다익스트라를 생각했었다. 

하지만 다익스트라의 경우에는 시작점이 존재하니까 불가능하다는 걸 알 수 있었다.  

 

조건에 나와있는 최소 유지비, 모든 정점을 연결, 양방향  을 통해 MST를 사용하면 된다는 걸 알 수 있었다.

 

=> 사용한 방법이 priority_queue를 이용해한 MST Prim방법이다. (MST - Prim 알고리즘)

 

다익스트라와 비슷한데, priority_queue에 pair<가중치, 도착점> 을 넣어주는 방식은 동일하지만, 기존에

가중치 = 간선의 가중치 + 앞선 노드 가중치  에서 

가중치 = 간선의 가중치 

만 사용해 주면 된다. 

 

그렇게 모든 마을을 잇는 하나의 최소 신장 트리를 찾고, 그 중 유지비가 높은 간선 하나를 제거하면 원하는 답을 찾을 수 있다. 

 

---

1. 임의의 시작점을 지정하고 그 점에서 가능한 모든 간선을 pq에 넣어준다. 

 

2. priority_queue를 이용한 다익스트라와 같은 방식을 사용해서 가장 유지비가 적은 노드에 접근하고 

그 노드의 간선을 pq에 계속 넣어준다. 

 

그 과정에서 나오는 유지비를 모두 ans 변수에 더하고 유지비 중 가장 큰 값을 minu 변수에 담는다.

 

3. 마지막으로 ans - minus를 하면 두 마을로 분리가 됨. 

 

[전체 코드]

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int N, M; // 집 개수, 길 개수
int visited[100002]; // 확인 및 유지비 기록


int main() {
	cin >> N >> M;
	
	priority_queue<pair<int, int>> q;
	vector<vector<pair<int,int>>> branch(N+1); //유지비, 도착 점

	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		branch[A].push_back({ C,B });
		branch[B].push_back({ C,A });
	}

	int start = 1;
	visited[start] = 1;
	for (int i = 0;i < branch[start].size();i++) {
		int C = branch[start][i].first;
		int next = branch[start][i].second;
		q.push({ -C,next });
	}

	int minu = 0;
	int ans = 0;

	while (!q.empty()){
		int C = -q.top().first;
		int start = q.top().second;
		q.pop();
		if (visited[start])continue;
		visited[start] = 1;
		ans += C;
		minu = max(minu, C);
		for (int i = 0;i < branch[start].size();i++) {
			int c = branch[start][i].first;
			int next = branch[start][i].second;
			if (visited[next])continue;
			q.push({ -c,next });
		}
	}

	cout << ans - minu;

}

 

 

[보완 및 고찰] 

Kruskal, Prim ... 예전에 한 번 공부한 적이 있었는데 오래되다 보니 기억이 가물가물.. 

 

 

++++

2. MST (최소 신장 트리)

그래프에서 비용 최소 비용 문제를 해결하기 위한 알고리즘

• • 1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  • 2) 두 정점 사이의 최소 비용 경로 찾기

​신장트리

• n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

​

2.1 KRUSKAL ( 단방향 간선 가능 )

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘

1) 최초, 모든 간선을 가중치에 따라 오름차순 정렬

2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

    - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택

3) n-1개의 간선이 선택될 때 까지 2)를 반복

 

[Kruskal]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 100001; 
int N, M; 
vector<pair<int, pii>> edges; 
int parent[MAX]; 
int answer = 0; 

void input() {
	cin >> N >> M; 

	// 부모 노드 배열 초기화 
	for(int i = 1; i <= N; i++){
		parent[i] = i; 
	}

	// 간선 정보 저장 
	for(int i = 0; i < M; i++){
		int a, b, c; 
		cin >> a >> b >> c;
		edges.push_back({c, {a, b}});
	}
}


// 루트 노드를 찾을 때까지 재귀 호출하고 
// 배열에 루트 노드 번호를 저장한다. 
int findRootNode(int x){
	if(x == parent[x]) return x;
	return parent[x] = findRootNode(parent[x]);
}

// 사이클을 만들지 않는 두 집합을 합친다. 
void unionSet(int a, int b) {
	if(a < b) parent[b] = a; 
	else parent[a] = b; 
}

void solution() {
	// 간선 비용을 기준으로 오름차순 정렬
	sort(edges.begin(), edges.end());

	// 간선 비용이 작은 것부터 MST에 포함시키기 
	int maxCost = 0;
	for(int i = 0; i < M; i++){
		int cost = edges[i].first; 
		int a = edges[i].second.first; 
		int b = edges[i].second.second; 

		// 사이클을 형성하지 않는 경우만 합친다.
		int rootA = findRootNode(a);
		int rootB = findRootNode(b);
		
		if(rootA != rootB){
			unionSet(rootA, rootB); 
			maxCost = max(maxCost, cost); 
			answer += cost; 
		}
	}

	// MST에 포함되는 간선 중에서 비용이 제일 큰 것은 제외한다. 
	cout << answer - maxCost;
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	input(); 

	solution(); 
	
	return 0; 
}