[백준/C++] 1277 - 발전소 설치

풀이 시간: 1:32:14

시간 복잡도: O(N^2)

공간 복잡도: O(N^2)

참고 자료: https://blog.naver.com/PostView.naver?blogId=gustn3964&logNo=222330297504

문제

엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 다시 연결하는게 현재 해결해야할 첫 번째 과제이다.

발전소는 1번부터 N번까지 번호로 매겨져 2차원 격자 좌표 위에 있다. 그리고 몇몇 전선은 보존된 채 몇몇 발전소를 잇고 있다. 문제는 현재 전선과 발전소의 위치가 주어졌을 때 최소의 전선 길이를 추가로 사용하여 1번 발전소와 N번 발전소를 연결짓는 것이다. 물론 연결 짓는 중간에 다른 발전소를 거쳐갈 수 있다. 단, 안정성 문제로 어떠한 두 발전소 사이의 전선의 길이가 M을 초과할 수는 없다. 아래에 이에 대한 예를 그려놓았다.

입력

첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발전소까지 각각의 발전소의 X좌표와 Y좌표(-100,000 ≤ xi,yi  ≤ 100,000)가 차례대로 주어진다. 다음 W개의 줄에 대해 각 줄에는 두 개의 정수가 입력되어지는데 이는 현재 남아있는 전선이 잇고 있는 두 발전소를 의미한다.

출력

첫 줄에 1번 발전소와 N번 발전소를 잇는데 필요한 추가 전선 길이의 최솟값을 1000배하여 출력한다. (단, 1000배하고 난 후 나머지 소수는 반올림이 아닌 버림을 한다)

문제 풀이

 

오류 원인

• 런타임 에러(OutOfBounds): findShortestNode 함수가 -1을 반환한 경우에 대한 예외 처리
• 해결 방안: if (newNode == -1) break;

전체 코드

/**
* 풀이 시간: 1:32:14
* 시간 복잡도: O(N^2)
* 공간 복잡도: O(N^2)
* 참고 자료: https://blog.naver.com/PostView.naver?blogId=gustn3964&logNo=222330297504
* [오류 원인]
* 런타임 에러(OutOfBounds): findShortestNode 함수가 -1을 반환한 경우에 대한 예외 처리
* 해결 방안: if (newNode == -1) break;
*/
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int INF = 1e9;

int N, W;
double M;
vector<bool> visited;
vector<double> dist;
vector<pair<double, double>> xy;
vector<vector<double>> node;

// 방문하지 않은 노드 중 가장 dist 값이 작은 노드의 인덱스 반환
int findShortestNode() {
	int minDist = INF, minIdx = -1;

	for (int i = 1; i <= N; i++) {
		if (visited[i] == true) continue;
		if (dist[i] < minDist) {
			minDist = dist[i];
			minIdx = i;
		}
	}
	return minIdx;
}

// 다익스트라 알고리즘을 사용하여 최단 경로 갱신
void dijkstra() { 
	// 시작 노드와 인접한 정점에 대한 거리 설정
	for (int i = 1; i <= N; i++) {
		dist[i] = node[1][i];
	}
    	// 시작노드에 관한 배열들 초기화
	dist[1] = 0;
	visited[1] = true;
    
    	// 새 노드 방문 및 최단 경로 계산
	for (int i = 1; i < N - 1; i++) {
		int newNode = findShortestNode();
		if (newNode == -1) break; // 값을 -1 반환할 경우 예외처리
		visited[newNode] = true;

		for (int j = 1; j <= N; j++) {
			if (visited[j] == true) continue; // 이미 방문한 노드일 경우 continue
            
            		// 시작 노드를 기준으로 새 노드를 거쳐서 j에 도달하는 경우 최단 거리 계산
			if (dist[j] > dist[newNode] + node[newNode][j])
				dist[j] = dist[newNode] + node[newNode][j];
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> W >> M;
	visited = vector<bool>(N + 1, false);
	dist = vector<double>(N + 1, INF);
	xy = vector<pair<double, double>>(N + 1);
	node = vector<vector<double>>(N + 1, vector<double>(N + 1, INF));

	// 각 좌표별 발전소 값 초기화
	for (int i = 1; i <= N; i++) {
		int x, y;
		cin >> x >> y;
		xy[i] = make_pair(x, y);
	}
	
    	// 2차원 벡터 node 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			double x = abs(xy[i].first - xy[j].first);
			double y = abs(xy[i].second - xy[j].second);

			// 두 발전소 사이의 전선의 길이가 M을 초과하면 안됨
			if (sqrt(x * x + y * y) <= M)
				node[i][j] = node[j][i] = sqrt(x * x + y * y);
		}
	}

	// 현재 남아있는 전선이 잇고 있는 두 발전소
	for (int i = 0; i < W; i++) {
		int a, b;
		cin >> a >> b;
		node[a][b] = node[b][a] = 0; // 이미 연결된 발전소들의 거리는 0으로 설정
	}

	dijkstra();
	cout << (long)(dist[N] * 1000) << endl;
}

 

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

1277번: 발전소 설치