1238 파티(C++)

1235번: 파티

다익스트라 알고리즘 응용 문제

규칙을 만족하는 최단거리를 구하는 문제

최단경로 문제 시리즈

1. 문제

---

간단 설명

이전에 풀었던 1753 최단경로 문제에

특정 조건들이 몇개 추가되었다

1. 각 마을에서 X번 마을로 가는 최단 경로를 구하고,

2. 다시 돌아오는 최단 경로를 구한뒤

3. 두 경로를 합한 값이 최대가 되는 값을 구하기

2. 문제 분석

---

주의점

1. 돌아오는 경로는 각 다익스트라 한번에 구할 수 있다

필요변수

• 마을 개수, 간선 개수, 파티장 X int N, M, X

• 간선 정보를 저장할 벡터 vector<pair<int, int >> map[MAX]

• 거리 정보를 저장할 int dist[MAX]

• 최대 거리를 저장할 int max_cost (첫번재 방식)

• 왕복 거리 정보를 저장할 int result[MAX] (두번째 방식)

3. 알고리즘

---

첫번째로 도전한 방식 : 우선순위 큐를 이용한 다익스트라 알고리즘

1. N, M, X 입력받기
2. 간선 정보를 map 벡터에 저장
3. 왕복 거리를 계산한다
    3-1. 다익스트라 알고리즘을 돌려 i에서 target까지의 최단거리를 구한다
    3-2. 다익스트라 알고리즘 한번 더 돌려 target에서 i까지의 최단거리를 구한다
    3-3. 구한 두 최단거리값을 저장된 최대 거리와 비교후 갱신한다

다익스트라를 모든 노드에 대해 계산시, 시간복잡도는

N번 반복 * O(E log V) 이므로 최대 2억정도라, 1초내애 통과 가능

이 방식도 문제는 통과했으나, 찾아보니 더 효율적인 방법이 있다

두번째로 도전한 방식

“출발점이 주어지면 그래프내의 모든 정점에 대한 최단경로가 단 한 번의 다익스트라 연산을 통해 구해진다”

N명의 학생이 X마을로 가는 다익스트라는 각각 구해야하지만,

X마을에서 돌아올때는 한번만 돌리면 된다

1. N, M, X 입력받기
2. 간선 정보를 map 벡터에 저장
3. 파티장으로 가는 각각의 최단거리를 계산하여 result 배열에 저장한다
4. 이후 파티장에서 다익스트라를 돌리면, 각 마을로 가는 최단거리가 계산된다
    - 이를 result 배열에 dist를 더해주면, 왕복 최단거리가 계산된다
5. 정렬후 최대값을 출력

4. 소스코드

---

첫번째로 도전한 방식

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

using namespace std;

#define MAX 1005

int N, M, target;
vector<pair<int, int>> map[MAX];
int dist[MAX];
int max_cost = 0;

void dijkstra(int start, int target) {
	// 1. dist 배열 INF로 초기화
	for (int i = 1; i <= N; i++) {
		dist[i] = 21e8;
	}
	// 2. pq 선언 후 시작 노드 넣기
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });// 시작점과 코스트를 저장. // 거리가 앞에 오도록 해야 정상동작함
	dist[start] = 0; // 시작 지점은 코스트 0

	while (!pq.empty()) {
		int curDist = -pq.top().first; // 음수로 저장해서 최소값을 뽑았으므로, 다시 양수화시킴
		int cur = pq.top().second; 
		pq.pop();

		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			int nextDist = map[cur][i].second;

			// 현재 노드의 이동거리와 다음 노드의 이동거리의 합이 저장된 값보다 작다면 교체
			if (curDist + nextDist < dist[next]) {
				dist[next] = curDist + nextDist;
				pq.push({-dist[next], next }); // 최소값을 뽑기 위해 음수화하여 저장
			}
		}
	}


}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> target;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a].push_back({ b, c });
	}

	// 왕복 거리를 계산해야한다
	// 1번부터 N번까지 
	// i 에서 target으로 가는데 걸리는 cost를 계산하고
	// target 에서 i로 돌아오는데 걸리는 cost 를 계산하여 더한 뒤 최대값인지 확인 
	for (int i = 1; i <= N; i++) {
		int cur_cost = 0;
		dijkstra(i, target);
		cur_cost += dist[target];
		dijkstra(target, i);
		cur_cost += dist[i];

		max_cost = max(max_cost, cur_cost);
	}

	cout << max_cost;

	return 0;
}

• dijkstra 함수에서 pair<int, int> 사용 시, 첫번째 인수에 거리를 넣어줘야 정상적으로 작동함

pair<int, int>형은 기본적으로 첫번째 원소 기준으로 정렬되기 때문

두번째로 도전한 방식

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

using namespace std;

#define MAX 1005

int N, M, target;
vector<pair<int, int>> map[MAX];
int dist[MAX], result[MAX];

void dijkstra(int start) {
	// 1. dist 배열 INF로 초기화
	for (int i = 1; i <= N; i++) {
		dist[i] = 21e8;
	}
	// 2. pq 선언 후 시작 노드 넣기
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });// 시작점과 코스트를 저장
	dist[start] = 0; // 시작 지점은 코스트 0

	while (!pq.empty()) {
		int curDist = -pq.top().first; // 음수로 저장해서 최소값을 뽑았으므로, 다시 양수화시킴
		int cur = pq.top().second; 
		pq.pop();

		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			int nextDist = map[cur][i].second;

			// 현재 노드의 이동거리와 다음 노드의 이동거리의 합이 저장된 값보다 작다면 교체
			if (curDist + nextDist < dist[next]) {
				dist[next] = curDist + nextDist;
				pq.push({-dist[next], next }); // 최소값을 뽑기 위해 음수화하여 저장
			}
		}
	}


}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> target;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a].push_back({ b, c });
	}

	// 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[j] = 21e8;
		}
		dijkstra(i);
		result[i] = dist[target]; // 
	}

	// 
	for (int j = 1; j <= N; j++) {
		dist[j] = 21e8;
	}
	dijkstra(target);

	for (int i = 1; i <= N; i++) {
		result[i] = result[i] + dist[i];
	}
	sort(result + 1, result + N + 1);
	
	cout << result[N];

	return 0;
}

• 2024-01-18 개선버전. 우선순위 큐를 오름차순으로 변경

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

using namespace std;

#define MAX 10001
#define INF 21e8

int N, M, X;
vector<pair<int, int>> map[MAX];
int dist[MAX];
int result[MAX];


// 시작지점부터 x까지의 최단거리를 찾는 다익스트라 함수
void dijkstra(int start) {
	// 1. dist 배열 초기화
	for (int i = 0; i <= N; i++) {
		dist[i] = 21e8;
	}
	// 2. 우선순위 큐 선언 및 초기세팅
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0, start });
	dist[start] = 0;

	// 3. 우선순위 큐 순회하면서 탐색
	while (!pq.empty()) {
		int curDist = pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		for (int i = 0; i < map[cur].size(); i++) {
			int nextDist = map[cur][i].first;
			int next = map[cur][i].second;

			if (curDist + nextDist < dist[next]) {
				dist[next] = curDist + nextDist;
				pq.push({ dist[next], next });
			}
		}
	}
}

int main() {
	// 1. 입력받기
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		map[start].push_back({ cost, end });
	}

	// 2. 각 마을에서 X까지 가는 다익스트라 계산
	for (int i = 1; i <= N; i++) {
		dijkstra(i);
		result[i] = dist[X];
	}
	
	// 3. 파티장 X에서 각 마을로 돌아오는 다익스트라 계산
	dijkstra(X);

	for (int i = 1; i <= N; i++) {
		result[i] += dist[i];
	}

	// 4. 최대값 찾기
	int max_cost = 0;
	for (int i = 1; i <= N; i++) {
		max_cost = max(max_cost, result[i]);
	}
	cout << max_cost;

	return 0;
}