백준 - 14938번, 서강그라운드 문제 풀이 - (C++)

이번에는 solved.ac에서 적당한 난이도의 문제를 고르다 class 4로 분류된 14938번 서강그라운드 문제가 적당히 풀만하지 않을까?라는 생각으로 풀어봤습니다.

 

난이도는 solved.ac 기준 골드 4로 class 4에 속한 평균적인 문제 같습니다.

 

14938번: 서강그라운드

---

문제 설명

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한 번도 치킨을 먹을 수가 없었다.

 

자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

 

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번, 2번(자기 지역), 3번, 5번 지역에 도달할 수 있다.

 

(4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.)

 

이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

---

입력

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

---

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

---

내가 풀이한 방식 정리

처음에는 어? 그냥 다익스트라나 bfs 뭐 이런 알고리즘 필요 없이 그냥 대강 시키는대로 구현하면 풀릴 것 같은데??라는 오만한 생각으로 모든 노드를 기준으로 유사 다익스트라 알고리즘을 적용해서 대강 현재 탐색 범위를 넘었으면 탐색 못하고, 저기를 탐색하면 탐색 범위가 이내이면 그냥 그 기준으로 탐색해서 queue에 넣는 방식으로 풀이를 했습니다..

 

하지만, 당연하게도 이렇게 풀면 최단 거리를 기준으로 탐색을 한 것이 아니기 때문에, 그 이후에 방문할 지역에 영향을 주게 되었고 10% 정도에서 오답 처리를 받게 되어 다익스트라로 구현 방향을 틀어서 제출했습니다.

 

문제는 기본적인 다익스트라 알고리즘을 구현할 수 있으면 풀이할 수 있는 문제였고, 어떻게 보면 문제 파악에 실패해서 오답을 받게 되었던 것 같습니다.

 

카카오 코테 이후로 학기를 보내면서 제대로 ps 공부를 하지 않았던 것 같다는 생각이 확 들어 앞으로는 학기 중에도 틈을 내어서 꾸준히 ps를 이어가며 간단하게라도 블로그에 정리하는 습관을 다시 들이려고 합니다!

 

제출한 코드에 특별히 포인트가 될만한 부분은 없는 것 같아 제출한 코드 첨부와 함께 글을 마무리 하도록 하겠습니다!

---

제출 코드 (C++)

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

#define MAX 101

using namespace std;

// n: 지역의 수, m: 수색 범위, r: 지역간 길의 수
int n, m, r;
int arr[MAX];
int res = 0;

vector<pair<int, int>> v[MAX];

void farming(int base) {
	queue<int> q;
	
	// 최대 거리는 1501
	int d[MAX];
	for (int i = 1; i <= n; i++) {
		d[i] = 1501;
	}

	d[base] = 0;

	int item = 0;

	q.push(base);

	while (!q.empty()) {
		int x = q.front();
		int dis = d[x];
		q.pop();

		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i].first;
			int next_dis = dis + v[x][i].second;

			if (d[y] <= next_dis)
				continue;

			d[y] = next_dis;
			q.push(y);
		}
	}
	//cout << "----------- base " << base << "----------" << endl;
	// base 위치를 기점으로 m 범위 이내에 도달 가능한 모든 지역의 아이템을 파밍한다.
	for (int i = 1; i <= n; i++) {
		if (d[i] <= m) {
			item += arr[i];
			//cout << "idx: " << i << " " << d[i] << endl;
		}
	}

	// 현재 지역을 기점으로 파밍한 결과가 좋은지 확인하고 갱신한다.
	res = (res > item) ? res : item;

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> r;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < r; i++) {
		int a, b, l;
		cin >> a >> b >> l;

		v[a].push_back({b, l});
		v[b].push_back({a, l});
	}

	for (int i = 1; i <= n; i++) {
		farming(i);
	}
	cout << res;

	return 0;
}