백준 14938 서강그라운드 C++

문제

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

---

입력

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

---

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

---

먼저, 지역이 있고, 각 지역마다 일정한 길이로 서로 연결되어 있습니다. 그리고 각 지역마다 연결된 길은 양방향으로,

통행이 가능합니다.

 

예은이는 특정 지역으로 낙하를 하는데, 거리가 수색범위 m이내의 모든 아이템을 획득 할 수 있습니다.

그림에서, 수색범위가 4이고, 예은이가 2번 지역에 떨어지게 된다면, 

1번,2번,3번 ,5번을 갈 수 있고 , 4번지역은 거리가 8이므로 갈 수 없습니다.

 

일단 플로이드-와샬로 2차원 배열 map[i][j]을 i에서 j로 가는 최단 경로로 만들어주었습니다.

ex(1,2) - > 1번지역에서 2번지역으로 가는 최단 경로

 

void floyd(){
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                map[i][j] = min(map[i][j],map[i][k] + map[k][j]);
            }
        }
    }
}

 

그 후, 예은이가 떨어진 지역이 1번 지역부터 ~ n번 지역까지 모두 가능하므로,

1번 지역부터 시작해서 n번 지역까지 대상으로,

수색 범위 안에 들어간다면, 그 지역에서 아이템을 먹을 수 있으므로, 해당 지역의 아이템을 더하였습니다.

그리고 해당 지역에 떨어졌으므로, 무조건 떨어진 지역의 아이템은 획득합니다.

 

ex) 1번 지역에 떨어진 경우 map[1][2] <= 수색범위(m) 이라면 2번지역의 아이템을 더하고,

map[1][3] <= m이라면 3번지역의 아이템을 더하고, map[1][4] <= m 이라면 4번 지역의 아이템을 더하고,

마지막에 떨어진 지역의 아이템을 더합니다.

 

-이 과정을 1부터 N까지 반복해서 최대로 획득한 아이템의 개수를 찾아내야 합니다 -

이 과정을 함수로 표현하자면 다음과 같습니다.

 

void solve(){
    for(int i = 0;i<n;i++){
    
    //1번부터 N번지역(0-N-1) 까지 예은이가 떨어질 수 있는 지역
    
        int temp = 0; //해당 지역에서 먹을 수 있는 아이템의 개수
        
        for(int j = 0;j<n;j++){ 
            if(map[i][j] <= m && i!= j){ 
            
            //수색범위 안에 들어온다면 j의 아이템을 가져감
                temp += items[j];
            }
        }
        temp += items[i]; //처음 떨어진 지역의 아이템은 무조건 획득함
        max_items = max(max_items,temp); //아이템의 개수 갱신
    }
}

 

 

최종적인 코드입니다.

 

#include <iostream>
#define MAX 987654321

using namespace std;

int l,m,n;
int map[101][101];//i에서 j로 가는 최단 경로
int items[101]; //해당 지역의 아이템의 개수
int max_items = -1; //아이템의 최대 개수(예은이가 얻을 수 있는)

int min(int a,int b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}

int max(int a,int b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}

void init(){
    cin >> n >> m >> l;
    for(int i = 0;i<n;i++){ //지역의 아이템을 입력받고
        cin >> items[i];
    }
    
    for(int i = 0;i<n;i++){ //플로이드 - 와샬 전 초기화
        for(int j = 0;j<n;j++){
            if(i!=j){
                map[i][j] = MAX;
            }
        }
    }
    
    for(int i = 0;i<l;i++){ //a에서 b로 가는 경로 (양방향)
        int a,b,c;
        cin >> a >> b >> c;
        map[a-1][b-1] = c;
        map[b-1][a-1] = c;
    }
    
}

void floyd(){
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                map[i][j] = min(map[i][j],map[i][k] + map[k][j]);
            }
        }
    }
}

void solve(){
    for(int i = 0;i<n;i++){
    
    //1번부터 N번지역(0-N-1) 까지 예은이가 떨어질 수 있는 지역
    
        int temp = 0; //해당 지역에서 먹을 수 있는 아이템의 개수
        
        for(int j = 0;j<n;j++){ 
            if(map[i][j] <= m && i!= j){ 
            
            //수색범위 안에 들어온다면 j의 아이템을 가져감
                temp += items[j];
            }
        }
        temp += items[i]; //처음 떨어진 지역의 아이템은 무조건 획득함
        max_items = max(max_items,temp); //아이템의 개수 갱신
    }
}
int main(void){
    init();
    floyd();
    solve();
    cout << max_items;
}