백준 1414 c++ "블우이웃돕기" -PlusUltraCode-

https://www.acmicpc.net/problem/1414

 

 

 

[필자 사고]

 

최소 스패닝 트리 알고리즘을 이용하여 푸는 문제이다.

 

알고리즘을 알고 문제를 풀면 쉽게 해결 하지만... 스패닝 트리라는걸 알기까지 과정이 힘들었따.

 

문제에서 핵심은 모든 컴퓨터가 랜선으로 서로서로 연결되어야 한다는 말이 있다.

 

이 부분을 Union 알고리즘을 이용하여 해결해 나갔다.

 

나머지 부분들은 랜선 길이를 기준으로 오름차순으로 정렬한뒤 
스패팅 트리 알고리즘을 이용하여 해결했다.
실수할 부분은 start지점하고 end지점이 같을 경우 제외해야 된다는 점이다.

 

아래는 코드 해설이다

 

1. Input 함수:

먼저 Input 함수에서, 우리는 목표 노드에서 출발하여 네트워크를 스캔합니다. 여기서 각 노드는 출발점이며, 그 노드와 연결된 다른 노드들의 가중치 정보를 받아옵니다. 각 문자를 소문자 또는 대문자로 분리한 후, 그 값을 arr라는 큐에 넣습니다. 이 큐는 다음 노드로 이동하기 전에 모든 연결 정보를 정렬할 수 있도록 준비하는 역할을 합니다. 모든 가중치는 누적되어 allLanSun에 더해집니다.

2. find 함수:

이 함수는 "현재 노드에서 이미 탐색한 경로가 있는지" 확인합니다. 목표 노드에서 출발할 때, 경로의 최종 루트 노드를 찾습니다. 만약 현재 노드가 다른 노드와 연결되어 있지 않다면, 그 노드 자체가 목표 노드가 됩니다.

3. isSame 함수:

여기서, "이동할 수 있는지 확인"하는 과정입니다. 현재 노드와 다음 노드가 동일한 그룹(즉, 이미 연결된 경로)이면 이동하지 않고, 그렇지 않으면 이동이 가능합니다. 이를 통해 불필요한 경로는 다시 방문하지 않도록 합니다.

4. Union 함수:

두 노드를 같은 그룹으로 묶는 역할을 합니다. 목표 노드에서 출발해 도착한 노드가 동일한 그룹에 속하지 않는다면, 두 노드를 연결합니다. 이는 두 노드를 하나의 경로로 묶어 최장 시간을 기록하는 과정이라고 볼 수 있습니다.

5. SpannigTree 함수:

여기에서 arr 큐에 있는 모든 경로들을 가중치가 적은 순서대로 정렬한 후, 출발 노드에서 목적지 노드로 이동합니다. 이 때, 현재까지 기록된 경로가 최장 시간일 때만 이동하는 방식으로 진행됩니다.
만약 같은 그룹에 속하는 경로는 이동하지 않고 무시되며, 새롭게 연결되는 경로만 최장 시간에 따라 이동하여 allLanSun에서 가중치를 빼줍니다. 즉, "최장 경로에서 최단 경로를 찾아 제거"하는 과정입니다.

6. GameStart 함수:

스패닝 트리 작업이 끝난 후, 모든 노드가 하나의 그룹으로 연결되었는지 확인하는 단계입니다. 여기서 연결되지 않은 노드가 있으면 이동하지 않고 바로 실패(-1)를 출력합니다. 모든 노드가 연결되었다면 최장 시간이 기록된 경로에 대한 결과가 출력됩니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
#include <algorithm>

using namespace std;

typedef struct Edge {
	int start;
	int end;
	int weight;
};

vector<Edge> arr;
vector<int> parent;
int N;
int allLanSun = 0;

bool cmp(Edge a, Edge b) {
	return a.weight < b.weight;
}


int find(int a) {
	if (a == parent[a]) {
		return a;
	}
	return parent[a] = find(parent[a]);
}
bool isSame(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return true;
	return false;

}
void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b)parent[b] = a;
}

void Input() {
	cin >> N;
	parent.resize(N);

	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < N; k++) {

			//소문자
			//대문자
			//0인경우
			char ch = str[k];

			if (ch >= 'a' && ch <= 'z') {
				int num = ch - 'a' + 1;
				arr.push_back({ i,k,num });
				allLanSun += num;

			}
			else if (ch >= 'A' && ch <= 'Z') {
				int num = ch - 'A' + 27;
				arr.push_back({ i,k,num });
				allLanSun += num;
			}

			else if (ch == '0') {
				continue;
			}
		}
	}


}

void SpannigTree() {
	sort(arr.begin(), arr.end(), cmp);

	for (int i = 0; i < arr.size(); i++) {
		Edge nowEdge = arr[i];
		int start = nowEdge.start;
		int end = nowEdge.end;
		int weight = nowEdge.weight;
		if (start == end)continue;


		if (isSame(start, end) == false) {
			Union(start, end);
			allLanSun -= weight;
		}
		else {
			
			continue;
		}
	}
}

void Print2() {
	cout << '\n';
	for (int i = 0; i < arr.size(); i++) {
		Edge nowEdge = arr[i];
		int start = nowEdge.start;
		int end = nowEdge.end;
		int weight = nowEdge.weight;

	}
}

void Print() {
	cout << '\n';
	for (int i = 0; i < N; i++) {
		cout << parent[i] << " ";
	}
	cout << '\n';
}


void GameStart() {
	SpannigTree();

	for (int i = 0; i < N; i++) {
		if (isSame(parent[0],parent[i]))continue;
		else {
			cout << "-1" << '\n';
			return;
		}
	}

	cout << allLanSun;
}


int main(void) {
	Input();
	GameStart();
}