BOJ 20007

03 Oct 2020 • ProblemSolving

떡 돌리기

문제출처

문제 해석

성현이가 N-1개의 집에 떡을 돌리기 위한 최소 일수를 구하는 문제입니다.

떡은 한번에 하나씩만 들고갈 수 있고, 하루에 X보다 먼 거리를 걷지 않고 가까운 집부터 방문합니다.

왕복할 수 없는 거리는 다음날 가기로 합니다.

설계(10)

간단하게 3가지 과정을 거치도록 설계하였습니다.

  1. 다익스트라 알고리즘을 사용하여 각 노드로 이동하기 위한 최단거리를 구합니다.O(MlogN) = O(10^6)

  2. 각 노드간 거리를 vector에 저장한 후, 거리가 짧은 순으로 정렬합니다.

  3. loop문 두개를 사용하여 X/2보다 작거나 같을 때까지 떡을 돌리고 일수를 증가시키는 방식으로 모든 곳에 떡을 돌릴 때까지 반복합니다.

지문에서 모두 방문할 수 없을 시 -1을 출력하라고 되어있습니다. 그러면 방문을 못하는 경우는 아래와 같이 생각할 수 있을 것입니다.

  1. 성현이 집에서 아예 못가는 경로로 되어있는 경우

  2. 성현이가 하루에 왕복할 수 있는 거리보다 긴 경우

위의 두가지 경우를 고려하여 예외처리를 해주면 구현이 완료됩니다.

구현(15)

코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 1000

vector<pair<int, int> > adj[MAXN];
int dist[MAXN];
vector<int> res;
priority_queue<pair<int, int> > pq;
int N, M, X, Y;
bool flag;
void dijkstra() {
	pq.push({ 0,Y });
	dist[Y] = 0;
	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (cur_dist != dist[cur]) continue;
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i].first;
			int next_dist = adj[cur][i].second + cur_dist;
			if (dist[next] == -1 || dist[next] > next_dist) {
				dist[next] = next_dist;
				pq.push({ -next_dist,next });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(dist, -1, sizeof(dist));
	cin >> N >> M >> X >> Y;
	while (M--) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
	}
	dijkstra();
	for (int i = 0; i < N; i++) {
		if (dist[i] == -1) {
			cout << -1 << "\n";
			return 0;
		}
		if (i == Y) continue;
		res.push_back(dist[i]);
	}

	sort(res.begin(), res.end());
	int idx = 0;
	int day = 0;
	while (idx < res.size()) {
		int cur_dist = X/2;
		while (idx < res.size() && cur_dist-res[idx]>= 0) {
			cur_dist -= res[idx++];
		}
		if (cur_dist == X / 2) {
			flag = true;
			break;
		}
		day++;
	}
	if (flag) cout << -1 << "\n";
	else cout << day << "\n";
	return 0;
}
디버깅
제출결과

40 ms

마무리

다익스트라의 전형적인 문제였습니다. 하지만 해당 알고리즘외에 조건을 만족하는 일 수를 찾기 위해서 별도로 처리해주어야하는 부분이 있었습니다.

 BOJ

Related Posts