[BOJ-2325] 개코전쟁(C++)

 

백준 2325 개코전쟁

 

2325번: 개코전쟁

 

문제 설명

 

 - 동물나라 지도에서 개미왕국은 1번 정점에 위치해 있고, 코끼리왕국은 N번 정점에 위치해 있다.

 

 - 개미왕국이 1번 정점에서 N번 정점으로 공격을 간다.

 

 - 개미 왕국은 최단 거리로 이동하고, 코끼리 왕국은 움직이지 않는다.

 

 - "앙두레 강"은 사자왕곡의 도움을 빌어 도로 중 딱 하는 파괴하여 개미왕국이 최단거리로 

   가더라도 그 거리를 최대로 만들려고 한다.

 

 - 어떤 하나의 도로를 파괴하더라도 1번 정점에서 N번 정점으로 도달 가능하다.

 

 - 적당한 도로 하나를 파괴했을 때 1번 정점에서 N번 정점으로의 최단 거리기의 최대값을 출력하라.

---

 

입력 값

 

 - 첫 줄에 N과 M이 입력된다. N은 정점의 개수이고, M은 도로의 수이다.

   ( 1 <= N <= 1000 / 1 <= M <= Nx(N-1)/2 )

 

 - 다음 줄부터 M개의 줄에 도로의 정보가 입력된다.

 

 - i+1번째 줄에는 i번째 도로의 정보 xi, yi, zi 가 입려되고 이 도로는 정점 xi와 정점 yi를 잇는 도로이며 지나는데 zi시간만큼 걸린다.

   ( 1 <= xi, yi <= N / 1<= zi <= 1000)

 

 - 두 정점 사이에는 두 개 이상의 길이 존재하지 않고, 모든 도로는 양방향이다.

 

 - 도로를 파괴하는 것은 양방향의 길 모두 파괴하는 것이다.

 

---

 

 

예제

---

 

 

문제 분석

 

 - 해당 문제는 1번 도시에서 N번 도시로 가는 최단 경로를 찾는 문제이다.

   도시의 가중치는 모두 양수이기 때문에 다익스트라를 이용하면 된다.

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra)

 

 - 다만, 중간에 도로 하나를 제거할 수 있다.

 

 - 도로 하나를 제거한 후 최단 경로를 찾고 해당 최단 경로 중 가장 큰 값을 찾는 문제이다.

 

 - 이 문제에서 가장 큰 문제는 어떠한 도로를 제거해야 하냐는 것이다.

 

 - 모든 도로를 제거하게 된다면, M의 최대 값 O($N^2$)의 경우의 수 만큼 살펴보아야 한다.

   즉, $N^2$의 경우에서 최단 경로를 모두 살펴보아야 된다. 그렇게 될 경우 시간초과가 발생한다.

 

 - 그렇다면 어떤 도로를 제거할 지 선택하는 기준은 어떻게 구해야 하는 것일까?

 

 - 그 힌트는 문제에 주어져 있다.

 

 - 개미왕국은 반드시 최단 경로로 코끼리 왕국(N번 도시)로 간다는 것이다.

 

 - 즉, 1번 도시에서 N번 도시로 가는 최단 경로가 아닌 도로를 제거해도 최소 값은 변하지 않는다는 것이다.

 

 - 결국 최단 경로 값을 변경하기 위해서는 1번 도시에서 N번 도시로 가는 도로들을 제거해야 한다는 것이다.

 

 - 문제를 푸는 과정은 다음과 같다.

   1. 다익스트라 알고리즘을 이용하여 1번 노드에서 N번 노드로 가는 최단 경로를 구한다.

      이때 각 노드들의 최단 경로 갱신 시 어떤 노드에서 왔는지 저장한다.

      ex) 3번 노드까지 오는 최단 경로는 1번 노드에서 3번 노드로 연결되었을 때 갱신된다 하면,

           arr[3]=1 형태로 저장한다.

 

   2. N번 노드부터 탐색하며, 최단 경로를 만드는 도로를 찾는다.

      직전 노드는 저장되어 있기 떄문에, 최단 경로를 바탕으로 찾으면 된다.

      ex) 최단 경로(최소 가중치 값)이 저장된 배열을 visited라 한다면,

           visited[3] = visited[1] + 1->3으로 가는 가중치 의 방식으로 찾을 수 있다.

 

   3. N번 노드부터 1번 노드까지 도로를 찾았다면, 해당 도로를 제거하고, 다익스트라 알고리즘을

      이용하여 1번 노드에서 N번 노드까지 최단 경로를 구한다.

 

   4. 구한 최단 경로 중 값이 가장 큰 값을 출력한다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v[1001];
int N, M;

int visited[1001];

// 최단 거리를 만들 때 selectNum[i]=j라고 하면
// i번째 노드를 거치기 전에 j를 거쳤다 j->i순으로 왔다.
int postIndex[1001];

int Dijkstra() {

	int nowVisited[1001];

	fill_n(nowVisited, 1001, INT_MAX);
	nowVisited[1] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,1 });

	while (!pq.empty()) {

		int nowCost = -pq.top().first;
		int nowIndex = pq.top().second;
		pq.pop();

		if (nowVisited[nowIndex] < nowCost) {
			continue;
		}

		for (auto next : v[nowIndex]) {
			int nextIndex = next.first;
			int nextCost = next.second;

			if (nextCost == -1) {
				continue;
			}

			if (nowVisited[nextIndex] > nowCost + nextCost) {
				nowVisited[nextIndex] = nowCost + nextCost;
				pq.push({ -nowVisited[nextIndex], nextIndex });
			}
		}
	}

	return nowVisited[N];


}

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

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a, b,c;
		cin >> a >> b>>c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	fill_n(visited, 1001, INT_MAX);
	visited[1] = 0;
	// 가중치, 인덱스
	priority_queue<pair<int,int>> pq;
	pq.push({ 0,1});

	while (!pq.empty()) {

		int nowCost = -pq.top().first;
		int nowIndex = pq.top().second;
		pq.pop();

		if (visited[nowIndex] < nowCost) {
			continue;
		}

		for (auto next : v[nowIndex]) {
			int nextIndex = next.first;
			int nextCost = next.second;

			if (visited[nextIndex] > nowCost + nextCost) {
				visited[nextIndex] = nowCost + nextCost;
				pq.push({ -visited[nextIndex], nextIndex });
				postIndex[nextIndex] = nowIndex;
			}
		}
	}

	int nowIndex = N;

	int result = 0;

	while (true) {

		if (nowIndex == 1) {
			break;
		}

		int postNum = postIndex[nowIndex];

		for (int i = 0; i < v[postNum].size(); i++) {

			pair<int, int> findNum = v[postNum][i];


			// 해당 인덱스인경우
			if (nowIndex == findNum.first && 
            		visited[nowIndex] - findNum.second == visited[postNum]) {

				v[postNum][i].second = -1;

				result = max(result, Dijkstra());

				v[postNum][i].second = findNum.second;

				nowIndex = postNum;

				break;

			}

		}

	}

	cout << result << "\n";


	return 0;
}