반응형

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

 

14938번: 서강그라운드

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을

www.acmicpc.net

 

 

[ 문제풀이 ]

 

데이크스트라를 이용하여 쉽게 풀 수 있는 문제입니다.

 

낙하 지역을 1부터 n까지 다 돌면서 데이크스트라를 적용시켜주면 됩니다. 거리 내에 있는 지역들을 들르면서 아이템의 개수를 더해주고, 거리를 벗어나면 continue 해주는 방법으로 문제를 풀었습니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {        //노드의 정보를 저장할 struct
    int to;            //다음 노드
    int dist;        //다음 노드까지의 거리
};
 
struct cmp {        //priority_queue 비교 연산자
    bool operator()(node right, node left)
    {
        return left.dist < right.dist;
    }
};
 
int n, m, r;
int item[101];        //각 지역의 아이템 수를 저장할 배열
vector<node> list[101];    //그래프
 
int main()
{
    cin >> n >> m >> r;
 
    for (int i = 1; i <= n; i++) {
        cin >> item[i];
    }
 
    for (int i = 0; i < r; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    int ans = 0;
 
    for (int i = 1; i <= n; i++) {    //모든 지역 탐색
        int cnt = 0;
        priority_queue < node, vector<node>, cmp> pq;
        int visited[101] = { 0 };
 
        pq.push({ i, 0 });
 
        while (!pq.empty())
        {
            int to = pq.top().to;
            int dist = pq.top().dist;
            pq.pop();
 
            if (visited[to] == 1 || dist > m) continue;    //방문했거나 거리가 멀면 continue
            visited[to] = 1;
            cnt += item[to];
 
            for (int i = 0; i < list[to].size(); i++) {
                int next = list[to][i].to;
                int nDist = list[to][i].dist;
                if (visited[next] == 0) {
                    pq.push({ next, nDist + dist });
                }
            }
        }
 
        if (ans < cnt) {
            ans = cnt;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27
[ 백준 ] 2618번 - 경찰차 (C++)  (0) 2022.07.26
[ 백준 ] 2150번 - Strongly Connected Component (C++)  (0) 2022.07.24
[ 백준 ] 1948번 - 임계경로 (C++)  (0) 2022.07.22
[ 백준 ] 10830번 - 행렬 제곱 (C++)  (0) 2022.07.21

+ Recent posts

티스토리툴바