백준 14983번 서강그라운드

 

 

 

문제 보러가기 : www.acmicpc.net/problem/14938

 

 

 

 

14938번: 서강그라운드

 

 

이번 문제는 다익스트라(Dijkstra) 문제였습니다.

 

다익스트라 기본 문제에서 각 지역의 아이템 개수를 담을 배열만 추가해주면 됩니다. 😊

 

 

 

 

《문제 풀이》

 

1. 길은 양방향 통행이 가능하므로 두 지역을 양방향으로 연결 

2. n개의 지역 중 습득 가능한 아이템의 최대 개수를 구해야 하므로 다익스트라 n번 수행

3. 낙하 지역을 제외한 모든 지역의 거리는 무한대로 초기화 (낙하 지역은 0)

4. 현재까지의 길이 + 다음 길이 < 다음 지역의 길이 라면 다음 지역의 길이 갱신

5. 갱신된 각 지역의 길이가 수색 범위보다 작거나 같다면 아이템 개수 더하기 ✨

6. 얻을 수 있는 아이템의 최대 개수 갱신 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 101
#define INF 987654321

using namespace std;

int n, m;
int arr[MAX];  
int dist[MAX];
vector<pair<int, int>> v[MAX]; // 지역 간 연결 정보   

void dijkstra(int start) {    
	queue<int> q;
	for(int i=1; i<=n; i++)
		dist[i] = INF;
	
	// 낙하 지역의 거리는 0  
	dist[start] = 0;
	q.push(start);
	
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		
		for(int i=0; i<v[node].size(); i++) {
			int nxtNode = v[node][i].first;
			int weight = v[node][i].second;
			
			// 최단경로라면  
			if(dist[node] + weight < dist[nxtNode]) {
				dist[nxtNode] = dist[node] + weight;
				q.push(nxtNode);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int r; 
	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 });
	}
	
	int result = 0;
	for(int i=1; i<=n; i++) {
		dijkstra(i); // 다익스트라 
		
		int sum = 0;
		for(int i=1; i<=n; i++) 
		      	// 수색 범위보다 작거나 같다면  
			if(dist[i] <= m)
				sum += arr[i]; // 아이템 개수 더하기  
	
		result = max(result, sum);
	}
	cout<<result;
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면