개요

백준 1162: 도로포장

• 입력
  첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

• 출력
  첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

접근 방식

1. 백준 15422: BUmped 문제처럼 포장된 도로를 탔을때 0으로 가야하는데 , 문제는 포장된도로를 한번만 타는게 아니라 k번 타야해서 감을 못잡았다..

2. 다른풀이를 보고 깨달았다.
   백준 15422: BUmped 문제에서는 그냥 2차원배열에서 행의 최대값을 2로 잡았지만, 이 문제에선 k가 최대 20이므로 행의 최대값을 20으로 잡으면 되는 것이다!

3. 일단 행값을 K으로 잡은 후, 도로를 포장할때마다 1씩 까면서 저장한다. 0번노드에서 N-1번노드까지 가는 방향이므로
   처음 시작은 minDist[K][0]=0으로 시작한다.

   	minDist[K][0] = 0;
   	pq.push({ 0, K*MAX});

4. 기본적으로 노드값 자체를 두가지 수(해당노드까지 도로포장한 갯수, 해당 노드) 이렇게 저장하므로 priority_queue에 저장을 할때
   MAX값으로 구별을 둬서 저장한다.

   do {
   	//MAX값으로 나눈값이 k값(행), MAX값으로 나눈 나머지가 curNode값 (열)이다. 
   	curK = pq.top().second / MAX;
   	curNode = pq.top().second%MAX;
   	pq.pop();
   } while (!pq.empty()&&visited[curK][curNode]);

   저장을 할때도 k값*MAX + nextNode이런식으로 저장을 한다.

   pq.push({minDist[curK][nextNode], curK*MAX+ nextNode});

5. 그 후, 우선순위큐에서 top노드를 꺼내고 , 해당 노드와 연결된 간선들을 방문했는지 체크한다.
   진행 가능하다면 포장을 안 한 상태로 nextnode로 진행후 최소거리가 갱신되면 저장 후, 우선순위큐에 푸시한다.

   for (auto& elem : adj[curNode]) {
   	int nextNode = elem.first;
   	long long dist = elem.second;
   	//포장안하고 탔을때 minDist[curK][nextNode]값이 갱신되면 갱신값 우선순위큐에 푸시
   	if (minDist[curK][nextNode] > minDist[curK][curNode] + dist) {
   	minDist[curK][nextNode] = minDist[curK][curNode] + dist;
   	pq.push({minDist[curK][nextNode], curK*MAX+ nextNode});
   }

   포장 안 한 상태로 진행 했으니, 포장을 하고 진행한다.

   //포장을 더 할수 있는 상태고, nextNode값까지 포장을 했을때 minDist[curK-1][nextNode]값이 갱신되면 갱신값 우선순위큐에 푸시
   if (curK-1 >= 0 && minDist[curK - 1][nextNode] > minDist[curK][curNode]) {
   	minDist[curK - 1][nextNode] = minDist[curK][curNode];
   	pq.push({ minDist[curK - 1][nextNode], (curK-1) * MAX + nextNode });
   }

6. 그 후, 도로포장을 한번도 안한 루트부터 k개 전부 다 포장한 루트까지의 최소값을 구해서 출력한다.

   long long Ans = INF;
   for (int i = 0; i < 20; i++) {
   	Ans = Ans > minDist[i][N - 1] ? minDist[i][N - 1] : Ans;
   }
   cout << Ans;

전체 코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;
int N, M, K;
const int MAX = 10'000;
long long INF = 1e12;
vector<vector<pair<int, int>>> adj;
priority_queue < pair<long long, long long>, vector<pair<long long , long long>>, greater<pair<long long, long long>>> pq;
long long minDist[21][MAX];
bool visited[21][MAX]={0,};
void Input() {
	int u, v, cost;
	cin >> N >> M >> K;
	adj.resize(N);
	for (int i = 0; i < M; i++) {
		cin >> u >> v >> cost;
		adj[--u].push_back({ --v,cost });
		adj[v].push_back({ u,cost });
	}
}

void Solution() {
	//초기화
	for (int i = 0; i <= 20; i++) {
		fill(minDist[i], minDist[i] + MAX, INF);
	}

	minDist[K][0] = 0;
	pq.push({ 0, K*MAX});
	while (!pq.empty()) {
		//minDist가 2차원행렬이라 k, node두값을 MAX로 곱해주는 형태로 나눠서 저장한다.
		int curNode=0, curK=0;
		do {
			//MAX값으로 나눈값이 k값(행), MAX값으로 나눈 나머지가 curNode값 (열)이다. 
			curK = pq.top().second / MAX;
			curNode = pq.top().second%MAX;
			pq.pop();
		} while (!pq.empty()&&visited[curK][curNode]);

		if (visited[curK][curNode]) break;
		visited[curK][curNode] = true;

		for (auto& elem : adj[curNode]) {
			int nextNode = elem.first;
			long long dist = elem.second;
			//포장안하고 탔을때 minDist[curK][nextNode]값이 갱신되면 갱신값 우선순위큐에 푸시
			if (minDist[curK][nextNode] > minDist[curK][curNode] + dist) {
				minDist[curK][nextNode] = minDist[curK][curNode] + dist;
				pq.push({minDist[curK][nextNode], curK*MAX+ nextNode});
			}
			//포장을 더 할수 있는 상태고, nextNode값까지 포장을 했을때 minDist[curK-1][nextNode]값이 갱신되면 갱신값 우선순위큐에 푸시
			if (curK-1 >= 0 && minDist[curK - 1][nextNode] > minDist[curK][curNode]) {
				minDist[curK - 1][nextNode] = minDist[curK][curNode];
				pq.push({ minDist[curK - 1][nextNode], (curK-1) * MAX + nextNode });
			}
		}
	}
	long long Ans = INF;
	for (int i = 0; i < 20; i++) {
		Ans = Ans > minDist[i][N - 1] ? minDist[i][N - 1] : Ans;
	}
	cout << Ans;
}

int main() {
	Input();
	Solution();
}

문풀후생

처음에 메모리초과가 계속떠서 매우 당황했다.

	//이렇게 풀면 오류남 why?
	//fill(&minDist[0][0], &minDist[20][10'001], INF);
	//fill(&visited[0][0], &visited[20][10'001], false);

처음에 이렇게 초기화를 했는데 메모리초과가 나서 다른부분을 손보다 혹시하고

	bool visited[21][MAX]={0,};

	for (int i = 0; i <= 20; i++) {
		fill(minDist[i], minDist[i] + MAX, INF);
	}

이런식으로 초기화를 했더니 통과가 되어서 이해가 안 갔었다.
예전문제들에선 저렇게 초기화를 했어도 통과가 되었어서 이 문서, 저 문서를 들여다 보다가 깨달았다,,

초기 선언을

const int MAX = 10'000;

long long minDist[21][MAX];
bool visited[21][MAX]={0,};

이렇게 열의 최대값을 10000으로 잡아놓고,
fill함수안에는 10001까지 초기화를 하라고해서 오류가 나는 것이였다,,,

진짜 사소한 부분이지만 그래도 한번 헤메게 되어서 다신 실수를 안 할 것 같다.. 다행이라고 생각한다.