[G4] 백준 20007번 떡 돌리기 C++ 다익스트라, 정렬

리뷰

 

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

처음엔 이해가 잘 가지 않았는데, 다익스트라로 최단거리 계산 후 정렬을 통해 그리디가 추가된 문제인 것 같다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• x : 하루에 갈 수 있는 거리의 최대값을 저장할 변수
• y : 시작 노드의 번호를 저장할 변수
• Edge : 간선 정보를 정의할 구조체
• edges : 간선 정보를 저장할 Edge타입 벡터 배열 인접리스트
• Pos : 현재 위치 정보를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

vector<int> dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ y, 0 });
	vector<int> dist(n, 2e9);
	dist[y] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv;
		if (dist[cn] < cv) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;

			if (dist[nn] > nv) {
				dist[nn] = nv;
				pq.push({ nn, nv });
			}
		}
	}
	return dist;
}

 

다익스트라를 통해 출발점으로 부터 모든 노드까지의 최단 거리를 구하고 반환하기 위한 함수

 

 

문제풀이

1. n, m, x, y값을 입력 받고, m개의 간선 정보를 입력 받아 edges배열을 초기화한다.
2. 정수형 벡터 dist를 dijkstra함수를 호출하여 반환받은 시작노드으로 부터 모든 노드까지의 최단 거리를 저장한다.
3. sort함수를 통해  dist벡터를 오름차순으로 정렬한다.
4. 변수 a, s를 0으로 초기화하고, 모든 노드를 순회하는 for문을 개행한다.
5. 변수 d에 현재 노드까지의 거리의 2배를 저장한다.
6. d가 x보다 크다면 해당 노드는 방문할 수 없으므로 -1을 출력하고 조기 종료한다.
7. s+d가 x보다 크다면 a를 증가시키고, s를 d로 저장한다.
8. s+d가 x보다 작거나 같다면 s에 d를 추가한다.
9. 모든 탐색을 마친 후 마지막으로 s가 0이 아닐경우 a를 증가시킨다.
10. a에 저장된 값을 출력한다.

 

트러블 슈팅

1. 다익스트라 내부에서 다음 간선의 가중치를 저장할때 nv = cn + edge.nv; 로 처리하여 WA를 받았다.
2. 간선의 가중치를 저장할때 nv = cv + edge.nv;로 올바르게 처리하여 제출하니 AC를 받았다.

 

참고 사항

1. 값의 범위는 (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)로 int자료형으로 처리 가능하다.
2. 잠은 꼭 본인 집에서 자야 한다. 떡은 한번에 하나씩만 들고 갈 수 있다.
3. 즉, 매번 자신의 집을 들려야 하므로 노드 방문 가중치는 최단 거리의 2배로 보는 것이 맞다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 1e3;
int n, m, x, y;
struct Edge {
	int nn, nv;
};
vector<Edge> edges[N];
struct Pos {
	int cn, cv;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

vector<int> dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ y, 0 });
	vector<int> dist(n, 2e9);
	dist[y] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.cn, cv = pos.cv;
		if (dist[cn] < cv) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.nn, nv = cv + edge.nv;

			if (dist[nn] > nv) {
				dist[nn] = nv;
				pq.push({ nn, nv });
			}
		}
	}
	return dist;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> x >> y;
	while (m--) {
		int f, t, v; cin >> f >> t >> v;
		edges[f].push_back({ t, v });
		edges[t].push_back({ f, v });
	}

	vector<int> dist = dijkstra();
	sort(dist.begin(), dist.end());

	int a = 0, s = 0;
	for (int i = 0; i < n; ++i) {
		int d = dist[i] * 2;

		if (d > x) {
			cout << -1;
			return 0;
		}

		if (s + d > x) {
			++a;
			s = d;
		}
		else s += d;

		//cout << a << " " << s << " " << d << "\n";
	}
	if (s) ++a;
	cout << a;
}