[Baekjoon/C++] 13141번 - Ignition

[백준] Baekjoon Online Judge

문제로 이동

 

문제

서훈이는 오늘 있었던 알고리즘 과목 기말고사를 망쳐서 기분이 좋지 않다. 서훈이는 스트레스도 풀 겸 시험 문제로 나온 그래프를 불로 태우려고 한다.

서훈이는 그래프의 정점 (위 그림에서 동그라미로 표시된 곳) 중 한 곳에 불을 붙일 수 있다. 정점에 불이 붙으면 곧바로 노드와 연결된 간선을 따라서 불이 전달된다. 간선 위에서는 불은 1초당 1만큼의 거리를 이동한다. 만약 어떤 간선의 양 끝 정점에 불이 붙은 경우 불은 간선의 중앙까지 태운 후 꺼진다.

서훈이는 그래프를 최대한 빠른 시간 안에 전부 태우고 싶어한다. 서훈이를 도와 어떤 정점에 불을 붙일지 구하는 프로그램을 작성하여라. 단, 위 그림에서 간선끼리 교차하는 것은 무시한다.

 

입력

첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000)

두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100)

시작점과 끝점이 같은 간선도 있을 수 있으며, 특정 두 정점을 직접 연결하는 간선의 수가 여러 개일 수 있다. 또한, 그래프의 모든 정점들은 간선들을 통해서 연결되어 있다.

 

출력

주어진 그래프를 모두 태우는 데 걸리는 최소 시간을 출력한다. 답은 소수점 아래 한 자리까지 출력한다. 문제의 특성 상 오차가 생길 일이 없으므로 출력 데이터와 정확히 일치해야 정답으로 처리한다.

 

---

풀이

#include <iostream>
#include <vector>
using namespace std;

#define INF 10000000

int N, M;
int edge[201][201];
vector<vector<int>> dist(201, vector<int>(201, INF));

double burn();

double burn() {
	double result = INF;

	for (int start = 0; start < N; start++) {
		double time = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (edge[i][j] == 0) continue; // 간선이 존재하지 않음

				// 두 정점 모두 불에 탔을 때 남은 간선의 길이
				double remain = edge[i][j] - (dist[start][j] - dist[start][i]);

				if (remain > 0) time = max((remain / 2 + dist[start][j]), time);
			}
		}

		result = min(result, time);
	}

	return result;
}

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

	cin >> N >> M;

	// 자기 자신과의 거리 체크
	for (int i = 1; i <= N; i++) dist[i][i] = 0;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		a--;
		b--;

		dist[a][b] = dist[b][a] = min(dist[a][b], c);
		edge[a][b] = edge[b][a] = max(edge[a][b], c);
	}

	// 플로이드-워셜
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	// 소수점 아래 한 자리까지 출력
	cout << fixed;
	cout.precision(1);
	cout << burn() << '\n';

	return 0;
}

 

	// 자기 자신과의 거리 체크
	for (int i = 1; i <= N; i++) dist[i][i] = 0;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		a--;
		b--;

		dist[a][b] = dist[b][a] = min(dist[a][b], c);
		edge[a][b] = edge[b][a] = max(edge[a][b], c);
	}

 간선의 정보를 입력 받는 부분의 코드이다. 정점을 태우는 가장 빠른 시간을 구하기 위해서는 가장 짧은 간선의 길이가 필요하고, 모든 간선을 태우는 시간을 구하기 위해서는 가장 긴 간선의 길이가 필요하다.

 

	// 플로이드-워셜
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

 플로이드 워셜 알고리즘으로 각 정점 사이의 최소 거리를 구한다.

 

double burn() {
	double result = INF;

	for (int start = 0; start < N; start++) {
		double time = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (edge[i][j] == 0) continue; // 간선이 존재하지 않음

				// 두 정점 모두 불에 탔을 때 남은 간선의 길이
				double remain = edge[i][j] - (dist[start][j] - dist[start][i]);

				if (remain > 0) time = max((remain / 2 + dist[start][j]), time);
			}
		}

		result = min(result, time);
	}

	return result;
}

 그래프를 모두 태우는 데 걸리는 최소 시간을 구하는 함수이다. 이때 두 정점 사이의 최소 거리와 두 정점을 연결하는 가장 긴 간선의 길이가 다르다면 두 정점이 모두 불에 탔음에도 간선이 모두 타지 않을 수  있다. 또한 두 정점에 모두 불이 붙었다면 간선이 타는 시간은 그 간선의 길이와 같지 않을 수 있다. 그렇기에 두 정점이 탔음에도 간선이 남았다면 (remain > 0) 그에 따른 시간 계산이 필요하다.