[백준] 14938번 : 서강그라운드 [C/C++]

#문제

14938번: 서강그라운드

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

14938번: 서강그라운드

 

---

#접근방법

모든 정점에서 모든정점으로 가는 최단경로를 구할 수 있는 최단거리 알고리즘을 사용하여야 한다.

모든 정점에서 모든 정점으로 가는 플로이드 워셜 알고리즘을 사용하여도 되고, 한 정점에서 모든 정점으로 가는 다익스트라 알고리즘을 반복문을 통하여 모든정점에서 출발시켜서 구하여도 된다.

 

아래 풀이는 다익스트라 알고리즘을 사용하였다.

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-CC

[백준] 1753번 : 최단경로 [C/C++]

다익스트라 알고리즘의 자세한 설명은 위 글을 참고하면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int item[105];
vector<pair<int,int> > node[105];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
int value[105];
int n,m,r;
int a,b,l;
int ans;

int Dij(int k){
    for(int i=1;i<=n;i++)
        value[i] = INF;

    value[k] = 0;

    pq.push(make_pair(0,k));

    while(!pq.empty()){
        int x = pq.top().first;
        int U = pq.top().second;
        pq.pop();

        for(int i=0;i<node[U].size();i++){
            int V = node[U][i].first;
            int W = node[U][i].second;

            if(x+W<value[V]){
                value[V] = x+W;
                pq.push(make_pair(x+W,V));
            }
        }
    }

    int sum = 0;

    for(int i=1;i<=n;i++){
        if(value[i]<=m)
            sum+=item[i];
    }

    return sum;
}

int main(){
    scanf("%d %d %d",&n,&m,&r);

    for(int i=1;i<=n;i++)
        scanf("%d",&item[i]);

    for(int i=0;i<r;i++){
        scanf("%d %d %d",&a,&b,&l);

        node[a].push_back(make_pair(b,l));
        node[b].push_back(make_pair(a,l));
    }

    for(int i=1;i<=n;i++)
        ans = max(ans,Dij(i));

    printf("%d",ans);

    return 0;
}

 

먼저 입력값을 입력받고, vector<pair<int,int> >형태의 배열에 길의 길이를 저장해준다. 양방향 통행이 가능하므로 a에서 b, b에서 a로 가는 경로를 저장시켜준다.

 

다익스트라 알고리즘은 한 정점에서 모든 정점으로의 최단경로를 구할 수 있다. 위 문제는 모든 정점에서 모든정점로의 최단경로를 구해야하므로 다익스트라 알고리즘을 함수화 하여 Dij(i)를 n번만큼 돌려서 구하도록 설계하였다.

 

Dij함수에서 k를 시작점으로 하여 다익스트라 알고리즘을 통하여 value배열에 최단경로를 구해준다.

 

value값이 수색범위 즉 m값 이하이면 수색가능하므로 item배열에 있는 값을 더해준다.

 

수색가능한 범위에서 최대한으로 아이템을 먹을 수 있는 값 sum을 반복문을 통해 모든 정점에서의 sum값 중 가장 큰 값을 구하여 ans에 저장시켜준다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

문제를 보고 최단거리 알고리즘을 생각 할 수 있는 것,

 

기본 알고리즘을 변형시켜서 사용할 수 있는 것,

 

이를 구현할 수 있는 능력이 있으면 풀 수 있는 문제였다.