[BOJ/Gold 4] 백준 20007 떡 돌리기(C++)

문제 링크

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

20007번: 떡 돌리기

문제

군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다. N-1개의 이웃집 모두에게 떡을 돌리기 위해서는 최소 며칠이 소요될 것인가.

집의 번호는 0번부터 N-1번까지 차례대로 붙어있다.

입력

첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)

두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주어진다. (0 ≤ A,B < N, 1 ≤ C ≤ 10,000) 단, A와 B는 서로 다른 수이고, C는 정수이다.

단, A집과 B집을 연결하는 도로는 유일하다.

출력

성현이의 집을 Y 라고 할 때, 이웃집 모두에 떡을 돌리기 위한 최소 일을 출력한다. 만약 모두 방문할수 없으면 -1을 출력한다.

예제 입력 1

5 6 21 0
0 1 6
0 2 3
0 3 10
1 2 2
2 4 7
3 4 8

예제 출력 1

3

예제 입력 2

6 5 10 4
0 4 6
0 5 2
1 3 1
1 5 8
2 3 1

예제 출력 2

-1

알고리즘 분류

• 최단 거리 알고리즘

풀이

다익스트라로 최단 거리를 구하고, 반복문을 통해 모든 집에 떡을 돌리면 몇 일이 소요되는 지 구한다.

만약 어느 한 집에 도달할 수 없거나, 왕복하는 데 걸리는 거리가 X를 넘어간다면 -1을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, X, Y;
vector<pair<int, int> > Edge[MAX];
int Cost[MAX];
vector<int> Cost_Vec;
bool Flag = true;
int IDX = 0;
int answer = 0;

void Input() {
	cin >> N >> M >> X >> Y;
	for (int i = 0; i < N; i++) {
		Cost[i] = INF;
	}
	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		Edge[A].push_back(make_pair(B, C));
		Edge[B].push_back(make_pair(A, C));
	}
}

void Dijkstra() {
	priority_queue<pair<int, int> > PQ;
	Cost[Y] = 0;
	PQ.push(make_pair(0, Y));

	while (!PQ.empty()) {
		int CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (Cost[CurX] < CurCost) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (Cost[nextX] > CurCost + nextCost) {
				Cost[nextX] = CurCost + nextCost;
				PQ.push(make_pair(-Cost[nextX], nextX));
			}
		}
	};
}

void Find_Answer() {
	for (int i = 0; i < N; i++) {
		if ((Cost[i] * 2 > X) || (Cost[i] == INF)) {
			Flag = false;
			break;
		}
		if (Cost[i] > 0) {
			Cost_Vec.push_back(Cost[i] * 2);
		}
	}
	if (Flag) {
		sort(Cost_Vec.begin(), Cost_Vec.end());
		while (1) {
			answer++;
			int CurX = X;
			while (1) {
				if (CurX < Cost_Vec[IDX]) {
					break;
				}
				CurX -= Cost_Vec[IDX++];
				if (IDX == Cost_Vec.size()) {
					break;
				}
			}
			if (IDX == Cost_Vec.size()) {
				break;
			}
		};
		cout << answer << "\n";
	}
	else {
		cout << -1 << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Dijkstra();
	Find_Answer();

	return 0;
}