[Java] 백준 14938 : 서강그라운드

 [문제]

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

14938번: 서강그라운드

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

[출력]

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

[예제 입력]

[풀이 과정]

수색범위 내에서 가장 많은 아이템을 먹었을 때의 결과값을 출력해주는 문제이다. 어디에 내려야 가장 많은 아이템을 얻는지 모르니 모든 정점에 대해서 한번씩 시작지점으로 잡고 다익스트라 알고리즘을 돌려주었다.  이 문제는 정점의 개수가 최대 100개기 때문에 플로이드-와샬 알고리즘을 이용해서도 풀 수 있다.

 

1. 해당 정점의 아이템 개수를 1차원 배열에 저장해둔다.

 

2. 시작 정점 n 을 기준으로 다익스트라 알고리즘을 실행한다.

    - 정점을 방문 했을때 얻을 수 있는 아이템의 수를 누적해서 저장해놓기 위해 변수를 선언하고 , 정점에 도착할때마다 해당정점의 아이템 개수를 누적하여 더한다. 정점에 왔을때 아이템 개수를 더할 수 있는 이유는 다익스트라는 한번 방문한 정점은 다시 최소비용으로 갱신되지 않기때문에 한번씩만 더하게 된다. 최단 거리의 비용으로 최소 비용을 갱신하기 때문이다.

   - 현재 정점을 기준으로 다음으로 이동할 정점을 찾을때 현재 정점까지 온 최소 비용 + 다음 정점으로 가는 비용이 수색범위 m보다 같거나 작을 경우만 우선수위 큐에 다음 정점 정보를 넣는다. 수색범위보다 높은 경로로 갈 수 없는게 문제의 조건이기때문이다.

 

3. 2번을 모든 정점 1~n 에 대하여 반복하여 최대 아이템 개수일 경우 정답을 갱신한다.

 

4. 최대 아이템 개수가 갱신이 되었다면 정답을 출력한다.

[코드]

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main14938 {

    static class Node {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
    public static void main(String[] args)  throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); //지역의 개수 (정잠)
        int m = Integer.parseInt(st.nextToken()); //수색 범위
        int r = Integer.parseInt(st.nextToken()); //길의 개수 (간선)


        st = new StringTokenizer(br.readLine());

        int []items = new int[n+1]; // 해당 정점에 몇개의 아이템 수가 있었는지 배열에 저장

        for(int i = 1; i<=n ;i++ ){
            items[i] = Integer.parseInt(st.nextToken());

        }

        //그래프 만들기

        ArrayList<Node> [] graph = new ArrayList[n+1];
        for(int i =1; i <=n;i++){
            graph[i]= new ArrayList<Node>();
        }

        for(int i = 0 ; i < r; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());


            //양방향 관계 설정
            graph[from].add(new Node(to,cost));
            graph[to].add(new  Node(from,cost));


        }

        int max =0; //최대로 얻을 수 있는 아이템 개수

        //어느 시작점 부터 내려서 이동해야 최대 아이템 개수를 얻을 수 있을지 구한다.
        //다익스트라 알고리즘을 이용하여 최소비용 내에 수색 범위 안에서 아이템의 개수를 구한다.

        for(int i = 1 ; i <=n ;i++){
            //큰 아이템 개수로 갱신한다.
              max = Math.max(max,dijkstra(n,i,graph,m,items));
        }


        //최대로 얻을 수 있는 아이템 개수를 출력한다.
        System.out.println(max);



    }

    private static int dijkstra( int n , int start, ArrayList<Node> [] graph ,int m,int[]items){

        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost,o2.cost));

        int count = 0;

        int []dist = new int[n+1];

        for(int i = 1; i<=n;i++){
            dist[i]= Integer.MAX_VALUE;
        }

        dist[start]=0;
        queue.add(new Node(start,0));

        while (!queue.isEmpty()){

            Node curNode = queue.poll();

            if(dist[curNode.idx] < curNode.cost ) continue;

            //현재 정점으로 들어왔다면 해당 정정에 있는 아이템 개수를 더한다.
            count+= items[curNode.idx];


            for(int i = 0 ; i < graph[curNode.idx].size(); i++){
                Node nxtNode = graph[curNode.idx].get(i);
                //다음 정점으로 이동하는 비용이 갱신되어있는 값보다 작을 경우만 더 탐색을 진행하고
                // 수색범위인 m보다 큰 경우면 탐색을 더이상 할 수 없다.
                if(dist[nxtNode.idx] > dist[curNode.idx] +nxtNode.cost &&dist[curNode.idx] +nxtNode.cost<=m ){
                    dist[nxtNode.idx]= dist[curNode.idx] +nxtNode.cost;
                    queue.offer(new Node(nxtNode.idx,dist[nxtNode.idx]));
                }
            }
        }

        return count;

    }
}

[결과]