[성실코딩 20일차] 백준 #1922 네트워크 연결 / 그래프

오랜만에 푸는 그래프 문제!! 

너무 오랜만이라서 데이터구조 수업 생각이 새록새록 났다

어렵지는 않지만 실행시간이 오래걸리는 것 같다

사용한 연결 선의 비용을 INF무한으로 바꿔주는 대신, 따로 저장하고 있는게 더 빠를까욤,,,?!!

아니면 모든 노드에 방문했는지 함수로 계속 확인해주는게아니라,

방문한 노드 갯수들 세고 있는게 더 빠를까욤,,?!!?

#include <iostream>

using namespace std;

#define INF 987654321

int n; // 컴퓨터의 수 <=1000
int graph[1001][1001];
bool visited[1001] = { false, };

bool allVisited() {
	for (int k = 1; k <= n; k++) {
		if (visited[k] == false) { 
			// 방문하지 않은 노드가 있다면
			return false;
		}
	}
	return true;
}

int main() {

	int m; // 선의 수
	cin >> n;  //컴퓨터의 수
	cin >> m;

	// 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF; // 최대값
		}
	}

	// 비용 입력받기
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
		graph[b][a] = c;
	}

	// 연산
	int cost = 0; // 전체 합 최소비용
	pair<int, int> minCostNode; // 다음에 연결 가능 선들 중 가장 최소 비용
	int minCost;
	
	visited[1] = true;
	while (1) {
		// 초기화
		minCost = INF;
		
		if (allVisited() == true) {
			break;
		}

		for (int from = 1; from <= n; from++) {
			if (visited[from] == true) {
				for (int to = 1; to <= n; to++) {
					if (from == to) {
						continue;
					}
					if (!visited[to] && graph[from][to] < minCost) { // 방문한적없고, 최소 비용
						// minCost update
						minCostNode.first = from;
						minCostNode.second = to;
						minCost = graph[from][to];
					}
				}
			}
		}

		// 
		cost += minCost;
		graph[minCostNode.first][minCostNode.second] = INF; // 사용한 연결선 다시 사용 못하도록
		graph[minCostNode.second][minCostNode.first] = INF;
		visited[minCostNode.second] = true; // 노드 방문 표시
	}

	// 출력
	cout << cost;
	return 0;
}