[백준 알고리즘] 14938번 - 서강그라운드

1. 문제 및 예시 실행결과

 

 다익스트라 문제라는 것을 처음부터 알게 되었다. 문제 잘 읽고 푸는 습관을 들여야하는데... 부등호하나 잘못써서 두번의 틀렸습니다가 찍힐뻔 했다... 다익스트라가 손에 조금 익어서 해당 알고리즘을 사용하고 있는데 플로이드 워셜로 나중에 공부해서 적재적소에 사용할 수 있으면 좋겠다.

 

출처: https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

---

---

2. 풀이 과정

 

 문제 쪼개기

 

1. 입력

2. 모든 노드를 시작점으로 설정

 - cache(최단거리 저장 배열) 초기화

 - dijkstra 진행

 - 해당 노드를 시작으로 하는 최단거리들을 기준으로 가질 수 있는 아이템 수 계산

 - ans와 비교

3. 출력

 

다음은 쪼갠 문제를 구현한 코드이다.

 

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

#define INF 987654321

using namespace std;

vector<pair<int, int>> graph[101];
vector<int> items;
int cache[101];

int main(void) {

	int n, m, r;
	int tmp;
	int start, end, weight;
	int ans = 0;

	cin >> n >> m >> r;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		items.push_back(tmp);
	}

	for (int i = 0; i < r; i++) {
		cin >> start >> end >> weight;
		graph[start].push_back(make_pair(end, weight));
		graph[end].push_back(make_pair(start, weight));
	}

	for (int i = 1; i <= n; i++) {
		//cache 초기화
		init_cache(n);

		//dijkstra 진행
		dijkstra(i);

		//최단거리의 범위 내에서 정담 count
		ans = max(ans, get_ans(n, m));
	}

	cout << ans;

	return 0;

}

 

양방향이어서 각 배열에 노드를 추가하였다. 다음은 구현한 함수들이다.

 

int get_ans(int n, int m) {
	int count = 0;
	for (int i = 0; i < n; i++) {

		if (cache[i + 1] <= m) {
			//cout << items[i] << ' ';
			count += items[i];
		}
	}

	return count;
}

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;

	pq.push(make_pair(0, start));
	cache[start] = 0;

	while (!pq.empty()) {
		int node = pq.top().second;
		int distance = -pq.top().first;
		pq.pop();

		for (int i = 0; i < graph[node].size(); i++) {
			int next_node = graph[node][i].first;
			int next_distance = distance + graph[node][i].second;

			if (next_distance < cache[next_node]) {
				cache[next_node] = next_distance;
				pq.push(make_pair(-next_distance, next_node));
			}
		}
	}
}

void init_cache(int n) {
	for (int i = 1; i <= n; i++) {
		cache[i] = INF;
	}
}

get_ans에서 모든 노드의 최단거리를 돌면서 기준 거리와 작거나 같으면 count에 더해주고 이를 return해준다. 다음은 전체코드이다.

 

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

#define INF 987654321

using namespace std;

vector<pair<int, int>> graph[101];
vector<int> items;
int cache[101];

int get_ans(int n, int m) {
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (cache[i + 1] <= m) {
			//cout << items[i] << ' ';
			count += items[i];
		}
	}
	return count;
}

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;

	pq.push(make_pair(0, start));
	cache[start] = 0;

	while (!pq.empty()) {
		int node = pq.top().second;
		int distance = -pq.top().first;
		pq.pop();

		for (int i = 0; i < graph[node].size(); i++) {
			int next_node = graph[node][i].first;
			int next_distance = distance + graph[node][i].second;

			if (next_distance < cache[next_node]) {
				cache[next_node] = next_distance;
				pq.push(make_pair(-next_distance, next_node));
			}
		}
	}
}

void init_cache(int n) {
	for (int i = 1; i <= n; i++) {
		cache[i] = INF;
	}
}

int main(void) {

	int n, m, r;
	int tmp;
	int start, end, weight;
	int ans = 0;

	cin >> n >> m >> r;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		items.push_back(tmp);
	}

	for (int i = 0; i < r; i++) {
		cin >> start >> end >> weight;
		graph[start].push_back(make_pair(end, weight));
		graph[end].push_back(make_pair(start, weight));
	}

	for (int i = 1; i <= n; i++) {
		//cache 초기화
		init_cache(n);

		//dijkstra 진행
		dijkstra(i);

		//최단거리의 범위 내에서 정담 count
		ans = max(ans, get_ans(n, m));
		//cout << ans << endl;

	}

	cout << ans;

	return 0;

}