[P4] 백준 13907번 세금 C++ 다익스트라, 다이나믹 프로그래밍

리뷰

 

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

슬슬 고난도 다익스트라 + DP문제도 어떻게 접근해야할지 최적해가 보이기 시작했다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• k : 쿼리의 개수를 저장할 변수
• s, d : 시작 지점과 도착 지점의 노드 번호를 저장할 변수
• Edge : 이동할 노드 번호와 간선의 가중치를 정의할 구조체, 간선의 가중치를 기준으로 오름차순 정렬한다.
• edges : 인접 리스트를 저장하기 위한 Edge타입 벡터 배열
• Pos : 현재 위치와 사용한 간선의 개수, 누적 가중치를 정의할 구조체, 누적 가중치 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

vector<int> dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ s, 0, 0 });
	vector<vector<int>> dist(n + 1, vector<int>(n + 1, 2e9));
	dist[s][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cc = pos.cc, cv = pos.cv;
		//cout << cn << " " << cc << " " << cv << "\n";

		if (cc >= n) continue;
		if (dist[cn][cc] < cv) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv, nc = cc + 1;

			if (dist[nn][nc] > nv) {
				dist[nn][nc] = nv;
				pq.push({ nn, nc, nv });
			}
		}
	}
	//cout << "done\n";

	return dist[d];
}

 

s에서 d까지 가는 사용한 간선의 개수별 최단 경로를 구하기 위한 함수

 

2. tax

int tax(vector<int>& dist, int val) {
	int ans = 2e9;
	for (int i = 0; i <= n; ++i) {
		dist[i] += i * val;
		ans = min(ans, dist[i]);
	}
	return ans;
}

 

간선의 가중치를 증가시키고 최단 경로를 최신화 하기 위한 함수

 

 

문제풀이

1. 전역 변수 n, m, k, s, d값을 순차적으로 입력 받아준다.
2. m개의 간선 정보를 입력 받아 인접 리스트 edges에 양방향 간선을 추가해 준다.
3. 1~n번 노드의 인접 리스트를 순회하며 sort함수를 통해 가중치를 기준으로 오름차순 정렬해 준다.
4. dijkstra함수를 호출하여 리턴값을 정수형 벡터 dist에 저장해 준다.
5. dijkstra함수가 호출되면 Pos타입의 우선순위 큐 pq를 초기화 하고, 초기값 {s, 0, 0}을 push해준다.
6. n+1*n+1크기의 2차원 벡터 dist를 초기값을 매우 큰 값으로 초기화해 주고, dist[s][0]를 0으로 초기화해 준다.
7. pq가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 꺼내어 변수 cn, cc, cv에 파싱해 준다.
8. cc가 n이상일 경우 continue처리해 주어 벡터 인덱스 범위를 넘어가지 않게 해준다.
9. dist[cn][cc]가 cv보다 작을 경우 continue처리해 주어 필요없는 탐색을 방지해 준다.
10. edges[cn]의 인접 리스트를 순회하며 변수 nn, nv, nc에 이동할 노드, 이동 후 누적 가중치, 간선 사용횟수를 저장한다.
11. dist[nn][nc]가 nv보다 클 경우 값을 갱신하고 pq에 nn, nc, nv를 push해준다.
12. while루프가 종료된 후 dist[d]벡터를 반환해 준다.
13. tax함수에 dist와 0을 매개변수로 전달하여 호출해 주고, 반환 값을 출력 후 개행문자를 삽입해 준다.
14. tax함수는 dist를 참조로 받고, val로 정수를 매개변수로 받는다.
15. 변수 ans에 초기값을 매우 크게 설정하여 초기화해 준다.
16. dist벡터를 순회하며 dist[i]에 i * val만큼 값을 더해주고 ans와 dist[i]중 작은 값을 ans에 저장해 준다.
17. dist순회를 마친 후 ans에 저장된 값을 리턴해 준다.
18. k번의 쿼리를 추가로 수행하고, 매 쿼리마다 변수 p에 인상 금액을 입력 받아준다.
19. tax함수에 dist, p를 매개변수로 호출하여 리턴값을 출력 후 개행문자를 삽입해 준다.

 

트러블 슈팅

1. dist벡터의 크기를 n+1*m+1로 설정하여 시간 초과를 받게 되었다.
2. 어차피 n개의 노드라면 최대 n-1개의 간선을 사용할 것이기 때문에 n+1*n+1 크기로 초기화 하여 AC를 받았다.

 

참고 사항

1. 다익스트라 내부의 dist값은 누적 가중치, 첫번째 인덱스는 현재 노드의 번호, 두번째 인덱스는 사용한 간선의 누적 개수를 의미한다.
2. 다익스트라 반환 후 dist값은 누적 가중치, 인덱스는 사용한 간선의 누적 개수를 의미한다.
3. 즉 한번의 다익스트라로 s번 노드에서 d번 노드로 이동하는 사용한 간선 개수별 누적 가중치를 구해준다.
4. 이후 세금이 올랐을 때에는 사용한 간선 개수를 기준으로 누적 가중치를 갱신 후 최단 경로를 구해주면 된다.

 

정답 코드

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

const int N = 1001;
int n, m, k, s, d;
struct Edge {
	int nn, nv;
	bool operator<(const Edge& other) const {
		return nv < other.nv;
	}
};
vector<Edge> edges[N];
struct Pos {
	int cn, cc, cv;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

vector<int> dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ s, 0, 0 });
	vector<vector<int>> dist(n + 1, vector<int>(n + 1, 2e9));
	dist[s][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cc = pos.cc, cv = pos.cv;
		//cout << cn << " " << cc << " " << cv << "\n";

		if (cc >= n) continue;
		if (dist[cn][cc] < cv) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv, nc = cc + 1;

			if (dist[nn][nc] > nv) {
				dist[nn][nc] = nv;
				pq.push({ nn, nc, nv });
			}
		}
	}
	//cout << "done\n";

	return dist[d];
}

int tax(vector<int>& dist, int val) {
	int ans = 2e9;
	for (int i = 0; i <= n; ++i) {
		dist[i] += i * val;
		ans = min(ans, dist[i]);
	}
	return ans;
}

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

	cin >> n >> m >> k >> s >> d;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	for (int i = 1; i <= n; ++i) sort(edges[i].begin(), edges[i].end());

	vector<int> dist = dijkstra();
	cout << tax(dist, 0) << "\n";

	while (k--) {
		int p; cin >> p;
		cout << tax(dist, p) << "\n";
	}
}