백준 14938 - 서강그라운드 (C++)

 

여러개의 노드와 간선의 정보가 주어진다.

 

이 때, 특정 노드에서 다른 노드로 이동 거리가 수색범위 m보다 더 크다면, 해당 노드의 아이템을 주울 수 없다.

여러 개의 노드 중, 어떤 노드에서 출발하여 수색을 해야 습득한 아이템의 총 개수가 가장 큰 지를 구하면 된다.

 

출력하는 것은 출발한 노드가 아니라, 획득한 아이템의 총 합이다.

 

문제 풀이

전형적인 최단거리 문제이다. 여러 알고리즘을 다 사용해도 되겠지만, 본인은 플로이드 워셜 알고리즘을 사용하였다.

입력 개수의 최대값이 지금처럼 크지 않을 땐, 플로이드 워셜을 사용하는 것이 좋다. 매우 구현이 간단하기 때문이다.

 

먼저, 주어진 간선의 정보를 이용하여 모든 노드와 노드사이의 최단 거리를 구한다.

 

이후, 최단 거리를 기반으로 특정 노드에서 시작했을 때, 아이템을 얼마나 습득할 수 있는지를 구한다.

이 과정을 모든 노드에 대해 검사하여, 아이템 습득량의 최대값을 구하면 된다.

 

풀이 코드

int NumField = 0;
int SeekRange = 0;
int NumRoad = 0;

std::cin >> NumField >> SeekRange >> NumRoad;

std::vector<int> Items(NumField);
for (int i = 0; i < NumField; i++)
{
    std::cin >> Items[i];
}

std::vector<std::vector<std::pair<int, int>>> Links(NumField);
for (int i = 0; i < NumRoad; i++)
{
    int Start = 0;
    int End = 0;
    int Weight = 0;

    std::cin >> Start >> End >> Weight;

    Start--;
    End--;

    Links[Start].push_back({ End, Weight });
    Links[End].push_back({ Start, Weight });
}

 

입력을 받는 코드이다.

먼저, 노드의 수와 수색 범위, 간선의 수를 입력받은 뒤, 각 노드에 아이템이 몇 개 있는지를 입력받는다.

이후, 간선의 정보를 입력받아서 Links라는 벡터에 저장하도록 하였다.

Start와 End에 --를 해주는 이유는 입력이 1부터 시작하기 때문이다.

std::vector<std::vector<int>> Cost(NumField, std::vector<int>(NumField, INT_MAX / 2 - 1));

for (int i = 0; i < NumField; i++)
{
    for (int j = 0; j < Links[i].size(); j++)
    {
        Cost[i][Links[i][j].first] = Links[i][j].second;
    }
}

이후, 노드간의 최단거리를 저장할 Cost벡터를 선언하였고, 입력받은 간선의 정보를 기반으로 Cost의 값을 초기화해주었다. 직접적으로 연결되어 있는 간선에 대해서만 Cost를 갱신한 것이다.

for (int i = 0; i < NumField; i++)
{
    for (int j = 0; j < NumField; j++)
    {
        for (int k = 0; k < NumField; k++)
        {
            Cost[j][k] = std::min(Cost[j][k], Cost[j][i] + Cost[i][k]);
        }
    }
}

 

이후, 플로이드 워셜 알고리즘을 사용하여 다른 노드를 거쳐서 도착하는 경우에 대해서도 Cost를 모두 갱신해주었다.

for (int k = 0; k < NumField; k++)
{
    Cost[k][k] = 0;
}

 

플로이드 워셜 알고리즘을 사용하고 나면 시작점과 도착점이 같은 경우에도 Cost가 갱신되어 있다.

하지만, 실제로는 시작점과 도착점이 같은 경우의 Cost는 존재하지 않기 때문에 이 값들을 0으로 바꿔주었다.

int MaxItemSum = 0;

for (int i = 0; i < NumField; i++)
{
    int CurItemSum = 0;

    for (int j = 0; j < NumField; j++)
    {
        if (Cost[i][j] <= SeekRange)
        {
            CurItemSum += Items[j];
        }
    }

    if (MaxItemSum < CurItemSum)
    {
        MaxItemSum = CurItemSum;
    }
}

 

위의 코드는 답을 구하는 코드이다.

i번 노드에서 시작했다고 했을 때, 수색 가능한 모든 노드에 존재하는 아이템의 개수를 CurItemSum에 누적하였다.

이후, CurItemSum이 MaxItemSum보다 더 크다면, MaxItemSum을 갱신하여 최대값을 저장해주었다.

std::cout << MaxItemSum;

return 0;

 

마지막으로 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumField = 0;
    int SeekRange = 0;
    int NumRoad = 0;

    std::cin >> NumField >> SeekRange >> NumRoad;
    
    std::vector<int> Items(NumField);
    for (int i = 0; i < NumField; i++)
    {
        std::cin >> Items[i];
    }

    std::vector<std::vector<std::pair<int, int>>> Links(NumField);
    for (int i = 0; i < NumRoad; i++)
    {
        int Start = 0;
        int End = 0;
        int Weight = 0;

        std::cin >> Start >> End >> Weight;
        
        Start--;
        End--;
        
        Links[Start].push_back({ End, Weight });
        Links[End].push_back({ Start, Weight });
    }

    std::vector<std::vector<int>> Cost(NumField, std::vector<int>(NumField, INT_MAX / 2 - 1));
    
    for (int i = 0; i < NumField; i++)
    {
        for (int j = 0; j < Links[i].size(); j++)
        {
            Cost[i][Links[i][j].first] = Links[i][j].second;
        }
    }

    for (int i = 0; i < NumField; i++)
    {
        for (int j = 0; j < NumField; j++)
        {
            for (int k = 0; k < NumField; k++)
            {
                Cost[j][k] = std::min(Cost[j][k], Cost[j][i] + Cost[i][k]);
            }
        }
    }

    for (int k = 0; k < NumField; k++)
    {
        Cost[k][k] = 0;
    }

    int MaxItemSum = 0;

    for (int i = 0; i < NumField; i++)
    {
        int CurItemSum = 0;

        for (int j = 0; j < NumField; j++)
        {
            if (Cost[i][j] <= SeekRange)
            {
                CurItemSum += Items[j];
            }
        }

        if (MaxItemSum < CurItemSum)
        {
            MaxItemSum = CurItemSum;
        }
    }

    std::cout << MaxItemSum;

    return 0;
}