C++로 풀어보는 밀 거래 최대 이익 계산 프로그램

n개의 도시가 m개의 도로로 연결되어 있다고 가정해 봅시다. 도로는 모두 단방향으로, 출발지에서 목적지로만 이동할 수 있고 반대 방향으로는 갈 수 없습니다. 도로 정보는 {출발지, 목적지} 형식의 배열 'roads'로 주어집니다.

각 도시에서는 밀이 서로 다른 가격에 거래됩니다. 배열 'price'의 i번째 값이 i번째 도시의 밀 가격을 나타냅니다. 여행자는 원하는 도시에서 밀을 사서, 도로가 허용하는 범위 내에서 다른 도시로 이동한 뒤 판매할 수 있습니다. 이때 여행자가 밀 거래를 통해 얻을 수 있는 최대 이익을 구하는 것이 문제의 목표입니다.

예시 입력과 출력

n = 5, m = 3, price = {4, 6, 7, 8, 5}, roads = {{1, 2}, {2, 3}, {2, 4}, {4, 5}}가 주어졌을 때 출력은 4입니다.

여행자가 첫 번째 도시에서 밀을 사서 네 번째 도시에서 판매하면, 총 이익은 8 − 4 = 4가 됩니다.

풀이 접근 방법

이 문제는 그래프를 순회하면서 각 도시에 도달하기 전까지 지나온 도시 중 가장 낮은 밀 가격을 추적하는 방식으로 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.

크기 n×n의 2차원 배열 graph를 정의한다.
i := 0부터 i < m까지 1씩 증가시키며 반복:
   x := roads[i]의 첫 번째 값
   y := roads[i]의 두 번째 값
   x, y를 각각 1씩 감소
   graph[x]의 끝에 y를 삽입
크기 n의 배열 tp를 음의 무한대 값으로 초기화
i := 0부터 i < n까지 1씩 증가시키며 반복:
   graph[i]의 각 값 u에 대해:
      tp[u] := min({tp[u], tp[i], price[i]})
res := 음의 무한대
i := 0부터 i < n까지 1씩 증가시키며 반복:
   res := max(res, price[i] - tp[i])
res 반환

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int m, vector<int> price, vector<pair<int, int>>
roads){
    vector<vector<int>> graph(n);
    for(int i = 0; i < m; i++){
        int x, y;
        x = roads[i].first;
        y = roads[i].second;
        x--, y--;
        graph[x].push_back(y);
    }
    vector<int> tp(n, int(INFINITY));
    for(int i = 0; i < n; i++){
        for(int u : graph[i]){
            tp[u] = min({tp[u], tp[i], price[i]});
        }
    }
    int res = -int(INFINITY);
    for(int i = 0; i < n; i++){
        res = max(res, price[i] - tp[i]);
    }
    return res;
}
int main() {
    int n = 5, m = 3;
    vector <int> price = {4, 6, 7, 8, 5};
    vector<pair<int, int>> roads = {{1, 2}, {2, 3}, {2, 4}, {4, 5}};
    cout<< solve(n, m, price, roads);
    return 0;
}

입력

5, 3, {4, 6, 7, 8, 5}, {{1, 2}, {2, 3}, {2, 4}, {4, 5}}