백준 10217(KCM TRAVEL)

jh Seo·2023년 6월 11일

다이나믹 프로그래밍 다익스트라 알고리즘 백준 한번에 못 푼 문제 한번에 푼 문제

백준

목록 보기

167/194

개요

백준 10217: KCM Travel

입력
입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수), 그리고 소요시간 d (1 ≤ d ≤ 1,000) 가 공백으로 구분되어 주어진다. 인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다
출력
각 테스트 케이스당 한 줄에 찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다.

만약, LA에 도착할 수 없는 경우 "Poor KCM"을 출력한다.

접근방식

다익스트라 알고리즘방식

백준 1162: 도로포장 문제와 유사해서 저 문제에서 학습한 방식대로 구현하였다.
저 문제에서 비용이 추가된 상황이므로,
처음 티켓값을 받을 때, 비용값까지 받는다.
```
struct ticket {
	int v;
	int c;
	int d;
};
```
이 문제도 백준 1162: 도로포장 문제와 마찬가지로 minDist배열을 2차원으로 두는 데, 차이점은 주어진 비용 M에서만 해결해야하므로
행을 비용으로 잡고, 열을 노드로 잡았다.
```
minDist[M][0] = 0;
pq.push({ minDist[M][0],M * MAX });
```

그 다음 과정을 동일하게 진행을 했으나 실수한 점은,
비용 M으로만 도착해야한다는 것이다.
백준 1162: 도로포장 문제에서는 포장을 아무것도 안하고 가는 경우도 존재해서 포장을 안하고 갈때와, 포장하고 갈때 두가지로 나눠야하지만 ,
이 문제에서는 무조건 비용을 사용하면서 가야한다.

for (auto& elem : ticketInfo[curNode]) {
	int nextNode = elem.v, nextDist = elem.d, nextCost = elem.c;

	//무조건 M원이하로 써야하기 때문에 어디로 가든 비용은 감소된다.
	//if (minDist[curM][nextNode] > minDist[curM][curNode] + nextDist) {
	//	minDist[curM][nextNode] = minDist[curM][curNode] + nextDist;
	//	pq.push({ minDist[curM][nextNode],curM * MAX + nextNode });
	//}
   
	//다음 간선으로 갈 비용이 존재하고, 다음간선으로 갔을때 minDist가 갱신이 된다면
	if ((curM >= nextCost) && (minDist[curM - nextCost][nextNode] > minDist[curM][curNode] + nextDist)) {
		minDist[curM - nextCost][nextNode] = minDist[curM][curNode] + nextDist;
		pq.push({ minDist[curM - nextCost][nextNode],(curM - nextCost) * MAX + nextNode });
		}
}

그 후 비용이 0남았을 때부터 M남았을 때까지 다 돌면서
답을 구한다.
만약 답이 전부 초기화값인 INF라면 갈 수 있는 루트가 존재하지 않으므로
"Poor KCM"을 출력한다.

int Ans = INF;
for (int i = 0; i < M; i++) {
	Ans = Ans > minDist[i][N - 1] ? minDist[i][N - 1] : Ans;
}
if (Ans == INF) cout << "Poor KCM" << '\n';
else cout << Ans << '\n';

다이나믹 프로그래밍 방식

매루트마다 비용을 사용하며 진행하므로 다이나믹 프로그래밍방식으로 풀 수 있다.
하지만 다이나믹프로그래밍 방식으로는 풀지 못해서 한번에 푼 문제와 한번에 못 푼 문제 둘다 태그가 되었다,,
위의 다익스트라 알고리즘 방식과 비슷하게 minDist를 INF로 초기화 시키고 진행하였다.
```
int KCM(int curMoney,int node) {
	int& ret = minDist[curMoney][node];
	if (ret != INF) return ret;
	if (node == N-1) return ret=0;

	for (auto& elem : ticketInfo[node]) {
		if (curMoney >= elem.c) ret = min(ret, KCM(curMoney -	 elem.c, elem.v)+elem.d);
	}	
	return ret;
}
```
위와 같은 다이나믹 프로그래밍 방식으로 진행하려 했으나 시간초과가 떠서
중간에 못 걸러냄을 파악했다.

다이나믹 프로그래밍 구조상 처음 if문을 통과했다면 밑에서 방문처리표시가 되어야 다음에 또 방문했을때 빠르게 걸러진다.

하지만 초기값을 INF로해버리면 if문을 통과후에, 만족하는 경로를 찾지못해서 ret값이 INF로 변함이 없다.
다음에 KCM(curMoney,node)을 방문했을때 그대로 INF값이 저장되어있어서 다시 코드를 진행하고 시간이 초과되는 것이다.
따라서 기본 초기값을 INF가 아니라 나올 수 없는 다른 값 (-1같은 값)저장해야 한다.
```
fill(&minDist[0][0], &minDist[MAX-1][100], -1);
```

그 후 , -1인지 검사하여 방문여부를 알 수 있었다.

//매 방문마다 현재 비용이 줄어들기 때문에, 다이나믹프로그래밍도 가능하다(knap-sack문제와 유사).
int KCM(int curMoney,int node) {
	int& ret = minDist[curMoney][node];
	if (ret != -1) return ret;
	if (node == N-1) return ret=0;
	//if 문 통과하고 INF값 저장
	ret = INF;
	for (auto& elem : ticketInfo[node]) {
		if (curMoney >= elem.c) ret = min(ret, KCM(curMoney -	 elem.c, elem.v)+elem.d);
	}	
	return ret;
}

다익스트라 알고리즘 방식 코드

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

using namespace std;
struct ticket {
	int v;
	int c;
	int d;
};

vector<vector<ticket>> ticketInfo;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int T, N, M, K,u,v,c,d;
const int MAX = 10'001;
const int INF = 1'000'000'000;
//행은 지원 비용, 열은 노드 
int minDist[MAX][100];
bool visited[MAX][100];

void Solution();

void Input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N >> M >> K;
		ticketInfo.clear();
		ticketInfo.resize(N);
		while (!pq.empty()) pq.pop();
		for (int j = 0; j < K; j++) {
			cin >> u >> v >> c >> d;
			ticketInfo[--u].push_back({ --v,c,d });
		}
		Solution();
	}
}

void Solution() {
	fill(&minDist[0][0], &minDist[MAX-1][100], INF);
	fill(&visited[0][0], &visited[MAX-1][100], 0);

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

	while (!pq.empty()) {
		int curM = 0, curNode = 0;
		do {
			curM = pq.top().second / MAX;
			curNode = pq.top().second % MAX;
			pq.pop();
		} while (!pq.empty() && visited[curM][curNode]);
		if (visited[curM][curNode]) break;
		visited[curM][curNode] = true;

		for (auto& elem : ticketInfo[curNode]) {
			int nextNode = elem.v, nextDist = elem.d, nextCost = elem.c;

			//무조건 M원이하로 써야하기 때문에 어디로 가든 비용은 감소된다.
			//if (minDist[curM][nextNode] > minDist[curM][curNode] + nextDist) {
			//	minDist[curM][nextNode] = minDist[curM][curNode] + nextDist;
			//	pq.push({ minDist[curM][nextNode],curM * MAX + nextNode });
			//}

			//다음 간선으로 갈 비용이 존재하고, 다음간선으로 갔을때 minDist가 갱신이 된다면
			if ((curM >= nextCost) && (minDist[curM - nextCost][nextNode] > minDist[curM][curNode] + nextDist)) {
				minDist[curM - nextCost][nextNode] = minDist[curM][curNode] + nextDist;
				pq.push({ minDist[curM - nextCost][nextNode],(curM - nextCost) * MAX + nextNode });
			}

		}
	}
	int Ans = INF;
	for (int i = 0; i < M; i++) {
		Ans = Ans > minDist[i][N - 1] ? minDist[i][N - 1] : Ans;
	}
	if (Ans == INF) cout << "Poor KCM" << '\n';
	else cout << Ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

다이나믹 프로그래밍 방식 코드

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

using namespace std;
struct ticket {
	int v;
	int c;
	int d;
};

vector<vector<ticket>> ticketInfo;
int T, N, M, K,u,v,c,d;
const int MAX = 10'001;
const int INF = 1'000'000'000;
//행은 지원 비용, 열은 노드 
int minDist[MAX][100];

void Solution();

void Input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N >> M >> K;
		ticketInfo.clear();
		ticketInfo.resize(N);
		for (int j = 0; j < K; j++) {
			cin >> u >> v >> c >> d;
			ticketInfo[--u].push_back({ --v,c,d });
		}
		Solution();
	}
}
//매 방문마다 현재 비용이 줄어들기 때문에, 다이나믹프로그래밍도 가능하다(knap-sack문제와 유사).
int KCM(int curMoney,int node) {
	int& ret = minDist[curMoney][node];
	if (ret != -1) return ret;
	if (node == N-1) return ret=0;

	ret = INF;
	for (auto& elem : ticketInfo[node]) {
		if (curMoney >= elem.c) ret = min(ret, KCM(curMoney -	 elem.c, elem.v)+elem.d);
	}	
	return ret;
}

void Solution() {
	fill(&minDist[0][0], &minDist[MAX-1][100], -1);

	int Ans = KCM(M, 0);
	if (Ans == INF) cout << "Poor KCM" << '\n';
	else cout << Ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

처음에 다이나믹 프로그래밍 방식으로 풀때 시작부터 틀렸습니다가 나와서 매우 당황했다.
두세시간 고민해서 알게된 건

const int MAX = 10'000;
int minDist[MAX][100];

minDist[MAX][100] 이렇게 선언돼서 minDist의 행의 값의 범위가
0~ 9999이다.
하지만 M의 범위는 1만까지고 처음 KCM(M,0);을 호출하면

int& ret = minDist[curMoney][node];

이 부분에서 minDist[10000][0]를 호출하게 되어서 엉뚱한 garbage값을
가져오는 것이였다.

여기서 이해 안 간 점은 대체 왜 범위를 벗어났는데 에러가 안뜨고 정상적으로 실행될까였다.

이 부분에 대한 해답은 [스택플로우 링크]에서 찾았는 데

요약해보면 Undefined behaviour로
몇 가지 원인을 추측해보면 배열은 c언어에서 옮겨온 것인데 ,raw memory를 사용하는 c의 구조상 범위를 벗어나는 지 체크하기 힘들다.
따라서 garbage값을 불러올 수 있다.

정도가 될 것같다.

결론은 그냥 사용자가 꼼꼼하게 주의해서 사용하던가 stl라이브러리의 vector을 사용하던가 정도가 될 것 같다.

실제로 지금 사용하는 비쥬얼스튜디오 2022환경에서

int main() {
	int min[4][2] = {0,};
	min[5][1] = 0;
	cout << min[5][1];
}

이 코드가 정상적으로 컴파일이 되고 실행이 된다.
물론 초록줄로 warning이 뜨지만, error가 아니라 실행은 된다.

jh Seo

코딩 창고!

이전 포스트

백준 1162(도로포장)

다음 포스트