[BOJ] 백준 14938번 : 서강그라운드 (JAVA)

문제

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

 

서강그라운드에서 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)가 주어진다.

 

 

출력

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

 

 

풀이

다익스트라 알고리즘을 활용하면 쉽게 풀 수 있는 문제였습니다. 다만, 문제에서는 수색할 수 있는 거리가 한정되어있었기때문에 dist 배열에서 수색할 수 있는 거리 이하의 지점의 아이템 개수만 파악하는 것이 중요했습니다.

(dist 배열은 어떤 지점에서 다른 모든 지점까지의 최단거리 정보를 담은 배열입니다.)

 

또한, 수색할 수 있는 거리 내에 갈 수 있는 지점이 있다면, 모두 방문할 수 있다는 점을 주의해야합니다. 저는 처음에 한 번만 갈 수 있는 줄 알고, 아이템의 누적 합을 구하는 뻘짓을 하여 몇 번 문제를 틀렸습니다. 우리 모두 문제를 꼼꼼히 읽도록 합시다.

 

위에서 언급할 내용을 조심하면, 다익스트라 알고리즘만 짜서 손 쉽게 해결할 수 있습니다.

 

아래 소스코드를 보시면서 참고하시길 바랍니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Position implements Comparable<Position> {
    int posNum; // 지역 번호
    int weight; // 거리
 
    Position(int posNum, int weight) {
        this.posNum = posNum;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Position arg0) {
        return weight - arg0.weight;
    }
 
}
 
public class Main {
    static int N, M, R; // 순서대로 지역의 개수, 수색 범위, 길의 개수
    static int[] item; // 각 지역마다 들어있는 아이템의 개수
    static ArrayList<ArrayList<Position>> a; // 인접리스트
    static int[] dist; // 최단거리 배열
    static boolean[] check; // 방문 확인
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
 
        item = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            item[i] = Integer.parseInt(st.nextToken());
        }
 
        a = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
        }
 
        // 양방향 인접리스트 구현.
        for (int i = 1; i <= R; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            a.get(start).add(new Position(end, weight));
            a.get(end).add(new Position(start, weight));
        }
 
        dist = new int[N + 1];
        check = new boolean[N + 1];
 
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dijkstra(i));
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 우선순위 큐를 활용한 다익스트라 알고리즘.
    public static int dijkstra(int start) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(check, false);
 
        PriorityQueue<Position> pq = new PriorityQueue<>();
        pq.offer(new Position(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Position curPos = pq.poll();
            int pos = curPos.posNum;
 
            if (!check[pos]) {
                check[pos] = true;
 
                for (Position position : a.get(pos)) {
                    if (!check[position.posNum] && dist[position.posNum] > dist[pos] + position.weight) {
                        dist[position.posNum] = dist[pos] + position.weight;
                        pq.add(new Position(position.posNum, dist[position.posNum]));
                    }
                }
            }
        }
 
        int res = 0;
        
        // 수색 범위 내로 갈 수 있는 모든 지역의 아이템 개수를 더함.
        for (int i = 1; i <= N; i++) {
            if (dist[i] <= M) {
                res += item[i];
            }
        }
 
        return res;
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.