[백준 5917] Roadblock

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

5917번: Roadblock

#include <cstdio>
#include <algorithm>
#include <queue>
int N, M;
int farm[100 + 10][100 + 10];
int chk[100 + 10];
int path[100 + 10];
int change[100 + 10];
int num;
int min_len;

struct _st
{
	int n;
	int d;
};

struct COMP
{
	bool operator()(_st &a, _st &b) {
		return a.d > b.d;
	}

};

using namespace std;

priority_queue<_st, vector<_st>, COMP> PQ;


void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int A = 0; int B = 0; int L = 0;
		scanf("%d %d %d", &A, &B, &L);
		farm[A][B] = L;
		farm[B][A] = L;
	}
}


int BFS(void)
{
	PQ = {};
	fill(chk + 1, chk + 1 + N, 0x7fffffff);

	PQ.push({ 1, 0 });	// 항상 존의 집에서부터 시작
	chk[1]= 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.n == N) return data.d;

		for (int i = 1; i <= N; i++) {
			if (farm[data.n][i] == 0) continue;	// 연결되지 않은 노드 건너뜀
			int nd = data.d + farm[data.n][i];
			if (chk[i] <= nd) continue;
			chk[i] = nd;
			path[i] = data.n;
			PQ.push({ i, nd });
		}
	}
}

void get_route(int n)
{
	if (n == 0) {
		return;
	}
	get_route(path[n]);
	change[num] = n;
	num++;
	//printf("%d ", n);
}


int get_min(void)
{
	int disturb = 0;
	for (int i = 0; i < num - 1; i++) {
		farm[change[i]][change[i + 1]] *= 2;
		farm[change[i + 1]][change[i]] *= 2;
		int sub = BFS() - min_len;
		disturb = (disturb < sub) ? sub : disturb;
		farm[change[i]][change[i + 1]] /= 2;
		farm[change[i + 1]][change[i]] /= 2;
	}
	return disturb;
}



int main()
{
	input();
	min_len = BFS();
	get_route(N);
	int ans = get_min();
	printf("%d\n", ans);
	return 0;
}

ㅇ...영어....=_=...

문제 설명을 대충하자면

FJ의 집 1에서 헛간 N으로 가는 최단 경로를 구하는 문제인데, 특정 두 노드 사이의 경로를 2배하여 ( "한 경로의 길이를 2배하여 구한 새로운 최단거리" - "집에서 헛간까지의 최단경로 길이") 의 최대값을 구해야 한다. 

 

 

// input( ) 함수

사실 인접리스트로 구현해보고 싶었지만 그건 실패했다.. 만약 해당 방법으로 푼다면 공유하겠다. 

farm이라는 인접행렬에 두 노드 A, B와 경로 L을 삽입한다. B 와 A 도 같은 거리만큼 떨어져 있으므로 반대로도 삽입해준다. 

 

 

// BFS( ) 함수

이 함수는 농부 존의 집 1에서부터 헛간 N까지의 최단경로를 구하는 일을 한다. 

이때 주의할 점은 한번 최단 경로를 구하고 더이상 함수를 쓰지 않는 것이 아니라, get_min 함수에서 계속해서 호출하기 때문에 PQ와 chk배열의 초기화가 항상 필요하다. 

한편 큐가 아니라 우선순위 큐를 사용했기 때문에, 모든 경로를 탐색하며 경우의 수를 따질 필요 없이 PQ에서 방금 뺀 데이터의 노드가 N과 같으면 바로 리턴해주어도 된다. 경로가 작은 것을 우선적으로 탐색하여 N까지 도달한 것이기 때문에, 더 진행하는 것이 의미가 없는 것이다. 

 

 

// get_route( ) 함수

사실 모든 경로를 2배씩 해서 그때마다의 최단 거리를 구해도 되지만... 이는 의미가 없다. 

예제를 살펴보자. 

// input
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

// output
2

이 경우 최단 거리는 6이고, 지나온 경로는 1 -> 3 -> 4 -> 5 이다. 

따라서 다른 간선을 2배해줘도 어차피 그쪽으로 가지 않을 것이기 때문에, 그때마다 최단 거리는 6이고 경로도 동일할 것이다. 

따라서 (1, 3) (3, 4) (4, 5) 노드 사이의 경로만 2배를 해주고, 각 경우들마다의 최단거리를 구해줄 것이다. 

 

 

// get_min( ) 함수

change는 지나온 경로{1, 3, 4, 5}가 들어있는 배열이다. 

두 노드 사이의 거리를 2배 해주고, 다시 BFS 함수를 호출하여 최단거리를 구해준다. 리턴값과 원래의 최단거리(min_len) 사이의 차를 sub 변수에 담아주었다. 

또한 그 차가 최대가 되는 경우를 출력해야 하기 때문에, disturb라는 변수에 차의 최댓값을 담아주도록 했다.

다음 두 노드 사이의 거리를 2배 해주고 BFS 함수를 호출하여 최단거리를 구하기 위해, 위에서 2배해주었던 경로들을 다시 2로 나누어 원래대로 바꿔주는 것이 필요하다.