[백준/c++] 14938 서강그라운드

✨ 문제 풀이

그래프와, 각 노드를 지나가는 간선의 비용이 있고, 비용의 합에 제한이 있을 때, 어떤 노드에서부터 순회를 시작하면 가장 많은 아이템(노드의 값)을 모을 수 있는지 물어보는 문제로 다익스트라를 이용해서 문제를 해결했다.

 

내가 해결한 방법은 아래와 같다.

1. 한 노드에 대해서 다익스트라 순회를 한다.
2. 다른 노드까지의 최소 거리를 d 배열에 저장한다.
3. d 배열에 저장된 간선 비용의 합 중에서, m보다 작은 노드들의 아이템 값을 합친다.
4. 모든 노드에 대해서 반복한다.
5. 가장 아이템값이 높은 값을 반환한다.

 

모든 노드에 대해서 순회하면서 거리의 비용을 계산해야 하므로 매번 다익스트라 순회를 해주기 전, d 배열의 값을 아주 큰 값(1억)으로 초기화해주는 작업을 했다. (최소 거리를 구하는 것이기 때문)

또한 최소 거리를 구하는 게 중요한 문제는 아니기 때문에 굳이 우선 순위 큐를 사용하지 않고, 일반 큐를 사용했다.

 

아래는 다익스트라 코드

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

#define MAXINT 1000000000
using namespace std;

int d[101];
vector<pair<int, int>> map[101];

void init()
{
    for (int i = 1; i <= n; i++)
        d[i] = MAXINT;
}

void dijkstra(int start)
{
    init();
    d[start] = 0;

    queue<pair<int, int>> pq;
    pq.push({start, 0});

    while (!pq.empty())
    {
        int current = pq.front().first;
        int distance = pq.front().second;
        pq.pop();

        if (d[current] < distance)
            continue;

        for (auto node : map[current])
        {
            int next = node.first;
            int nextDistance = distance + node.second;
            if (nextDistance < d[next])
            {
                d[next] = nextDistance;
                pq.push({next, nextDistance});
            }
        }
    }
}

 

🗓 코드

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

#define MAXINT 1000000000

using namespace std;

int n, m, r;
int t[101];
int d[101];
vector<pair<int, int>> map[101];

void getInput()
{
    cin >> n >> m >> r;
    for (int i = 1; i <= n; i++)
        cin >> t[i];
    for (int i = 1; i <= r; i++)
    {
        int a, b, l;
        cin >> a >> b >> l;
        map[a].push_back({b, l});
        map[b].push_back({a, l});
    }
}

void init()
{
    for (int i = 1; i <= n; i++)
        d[i] = MAXINT;
}

void dijkstra(int start)
{
    init();
    d[start] = 0;

    queue<pair<int, int>> pq;
    pq.push({start, 0});

    while (!pq.empty())
    {
        int current = pq.front().first;
        int distance = pq.front().second;
        pq.pop();

        if (d[current] < distance)
            continue;

        for (auto node : map[current])
        {
            int next = node.first;
            int nextDistance = distance + node.second;
            if (nextDistance < d[next])
            {
                d[next] = nextDistance;
                pq.push({next, nextDistance});
            }
        }
    }
}

int getNumberOfItemsFromStart(int start)
{
    dijkstra(start);

    int items = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] <= m)
            items += t[i];
    return items;
}

int getMaxItemsNumber()
{
    int maxItems = -1;
    for (int i = 1; i <= n; i++)
    {
        int tempItems = getNumberOfItemsFromStart(i);
        if (maxItems < tempItems)
            maxItems = tempItems;
    }
    return maxItems;
}

int main(void)
{
    getInput();
    int answer = getMaxItemsNumber();
    printf("%d\n", answer);
    return 0;
}