BOJ 10217 KCM Travel

11 Jun 2019 in Study on BOJ, Dp, Dfs, 다익스트라

방법 1

사용한 알고리즘

다익스트라 알고리즘

알고리즘 설명

각 도시를 노드로 하며 그 사이를 (거리, 시간) 가중치로 연결시켜 그래프를 구성한다.
시작 도시로 부터 다익스트라 알고리즘을 적용한다. 여기서 dist(도시,남은 돈)으로 dist를 구성한다.
비행기를 탈 수 있다면, dist(다음 도시, 남은 돈-비행기값) > dist(현재 도시, 남은돈) + 비행기 시간를 조건으로 최단거리를 구해간다.
N번째 도시를 업데이트 했을 때가 가장 빠른 도착 시간이며, 도착하지 않고 큐가 비어있게 되면 갈 수 없으므로 “Poor KCM”를 출력한다.

풀이

// baekjoon 10217 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

struct pqitem{
	int d, c, v;
};

bool operator<(const pqitem& a, const pqitem& b) {
	return a.d > b.d;
}

const int MAX_N=101;
const int MAX_M=10001;
const int MAX_INF=2139062143;

int T, N, M, K, u, v, c, d;
int dist[MAX_N][MAX_M];
bool visited[MAX_N][MAX_M];
vector<vector<pqitem> > adj;

int Dijkstra() {
	memset(dist, 0x7F, sizeof(dist));
	memset(visited, 0, sizeof(visited));

	priority_queue<pqitem> PQ;
	dist[1][M]=0;
	PQ.push({0, M, 1});
	while (!PQ.empty()) {
		int cur_N, cur_M, cur_D;
		do {
			cur_D = PQ.top().d;
			cur_N = PQ.top().v;
			cur_M = PQ.top().c;
			PQ.pop();
		} while (!PQ.empty() && visited[cur_N][cur_M]);
		if (visited[cur_N][cur_M]) break;
		if (dist[cur_N][cur_M] < cur_D) continue;
		if (cur_N == N) return dist[cur_N][cur_M];
		visited[cur_N][cur_M]=true;
		for (int i=0; i<adj[cur_N].size(); i++) {
			int n_N = adj[cur_N][i].v;
			int p_c = adj[cur_N][i].c;
			int p_d = adj[cur_N][i].d;
			if (p_c > cur_M) continue;
			if (dist[n_N][cur_M-p_c] > dist[cur_N][cur_M] + p_d) {
				dist[n_N][cur_M-p_c] = dist[cur_N][cur_M] + p_d;
				PQ.push({dist[n_N][cur_M-p_c], cur_M-p_c, next_N});
			}
		}
	}
	return MAX_INF;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &N, &M, &K);
		adj = vector<vector<pqitem> >(N+1);
		while (K--) {
			scanf("%d%d%d%d", &u, &v, &c, &d);
			adj[u].push_back({d, c, v});
		}

		int ret = Dijkstra();
		if (ret == MAX_INF) puts("Poor KCM");
		else printf("%d\n", ret);
	}
	return 0;
}

방법 2

사용한 알고리즘

DP, DFS

알고리즘 설명

DP로 점화식을 새워서 DFS 형태로 풀어가는 방법이다.
DP(i,j)로 i번째 도시가 돈을 j만큼 사용했을때 도착점까지 거리
DP(i,j) = min(dp(node, cost + j) + distance):(cost, distance, node) <- (plane(i))
위 점화식을 DFS로 풀어낸다. 이는 cost가 항상 1보다 크기 때문에 가능하다.

풀이

// baekjoon 10217 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

const int MAX_N=101;
const int MAX_K=10001;

int T, N, M, K, ans, u, v, c, d; // cost, delay
int dp[MAX_N][MAX_K]; // [node][money]
vector<vector<pair<pair<int,int>,int> > > adj; // [[cost, distance], node]
int dfs(int here, int cost) { // current cost
	if (cost > M) return 1e9;
	if (here == N) return 0;
	int &ret = dp[here][cost];
	if (ret != -1) return ret;
	ret = 1e9;
	for (int i=0; i<adj[here].size(); i++) {
		int nx = adj[here][i].second;
		int nc = adj[here][i].first.first;
		int nd = adj[here][i].first.second;
		ret = min(ret, dfs(nx, cost + nc) + nd);
	}
	return ret;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		memset(dp, -1, sizeof(dp));
		scanf("%d%d%d", &N, &M, &K);
		adj = vector<vector<pair<pair<int,int>,int> > >(N+1);
		for (int i=0; i<K; i++) {
			scanf("%d%d%d%d", &u, &v, &c, &d);
			adj[u].push_back({ {c,d}, v});
		}
		ans = dfs(1, 0);
		if (ans == 1e9) puts("Poor KCM");
		else printf("%d\n", ans);
	}
	return 0;
}