[BOJ-2157] 여행(JAVA)

백준 2157 여행

 

2157번: 여행

 

문제 설명

 

 - N개의 도시가 동쪽에서 서쪽으로 순서대로 위치해 있다.

 

 - 제일 동쪽은 1번 도시이며, 제일 서족은 N번 도시이다.

 

 - 이 도시 중 M개 이하의 도시를 지나는 여행을 계획하려 한다.

 

 - 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시로 끝나야 한다.

 

 - 1번 도시와 N번 도시도 M개의 도시에 포함된다.

 

 - 동쪽으로 갔다가 서쪽으로는 갈 수 없기 때문에 계속 서쪽으로만 가야 한다.

   즉, 도시 번호가 증가하는 순서대로만 이동할 수 있다.

 

 - 도시를 이동할 때 비행기를 이용하는데, 최대한 맛있는 기내식만 먹으면서 이동하려 한다.

 

 - 항로 개설 여부와 해당 항로에서 제공되는 기내식의 점수가 주어졌을 때, 먹게 되는 기내식 점수의 총 합이 최대가 되도록 하라.

 

---

 

입력 값

 

 - 첫째 줄에 N, M, K 가 주어진다.(K는 개설된 항공로의 개수이다.)

    ( 1 <= N <= 300 / 2 <= M <= N / 1 <= K <= 100,000 ) 

 

 - 다음 K개의 줄에는 각 항공로에 대한 정보가 세 정수 a, b, c로 주어진다.

   ( 1 <= a, b <= N / 1 <= c <= 10,000 )

 

 - a번 도시에서 b번 도시로 이동하는 항로가 있고, 기내식 점수는 c이다.

 

 - 서쪽에서 동쪽으로 이동하는 항로가 입력될 수도 있고, 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있다.

 

 - 다시 원래 도시로 돌아는 a=b 와 같은 입력은 주어지지 않는다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제에서 주의해야 할 점은 도시간 이동 시 반드시 서쪽으로 이동해야 한다는 것이다.

 

 - 즉, 도시 번호가 작은 것에서 큰 것으로 이동한다는 것이기 때문에 입력 받을 때 서쪽에서 동쪽으로 이동하는

   경로는 제외해야 한다.

 

 - 이 문제는 간단하게 생각하면, BFS를 이용하여 풀 수 있다.

탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS)

 

 - 1번 도시를 시작으로 서쪽으로 가는 경로를 탐색하며, M개의 도시를 지날 때 까지 기내식의 점수를 계속 더한다.

   그리고 N번 도시를 방문하는 경우 그 값을 큰 것으로 계속 갱신한다.

 

 - 이렇게 단순하게 접근할 경우 중복되는 부분이 많이 발생한다.

 

 - 예를 들어 3번만에 5번 도시에 도착한 경우 기내식 점수가 10점이라 가정하자

   그렇다면, 그 이후에 3번만에 5번 도시에 도착한 경우 기내식 점수가 10점 이하인 경우는 고려할 필요가 없다.

 

 - 왜냐하면, 어차피 그 이후에 가는 경로는 그 이전에 왔던 경로와 상관없기 때문이다.

 

 - 즉, 이 문제는 메모이제이션을 이용한 DP 문제라고 볼 수 있다.

다이나믹 프로그래밍(Dynamic Programming, DP)

 

 - DP[M][N] = N번째 도시에 도착하고 지나온 도시가 M개일 떄 기내식 점수의 최댓값이라고 설정할 수 있다.

 

 - 결론적으로 문제를 푸는 방법은

    1. 1번 노드를 시작으로 BFS를 시작한다.

    2. DP[M][N] 의 값을 갱신할 수 있는 경우에만 다음 노드를 탐색한다.

    3. M번 도시를 방문한 경우를 모두 살펴본 후 DP[1][N] ~ DP[M][N] 값 중 가장 큰 값을 리턴한다. 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// https://www.acmicpc.net/problem/2157
// 여행
public class Main {

    private static int dp[][];

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // DP[M][N] = M번 도시 방문 했을 때 도착 도시 번호가 N
        dp = new int[M+1][N+1];

        List<Node> boards[] = new List[N+1];

        for(int i=0;i<=N;i++){
            boards[i]=new ArrayList<>();
        }

        for(int i=0;i<K;i++){

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

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if(a > b){
                continue;
            }

            boards[a].add(new Node(b,c));
        }

        int result=0;

        Queue<Integer> q = new LinkedList<>();

        q.add(1);

        int cnt=1;

        while(!q.isEmpty() && cnt < M){

            int size = q.size();

            while(size-- > 0){
                int nowIndex = q.poll();
                for(Node nextNode : boards[nowIndex]){

                    int nextIndex = nextNode.index;
                    int nextScore = dp[cnt][nowIndex]+nextNode.score;

                    if(dp[cnt+1][nextIndex] >= nextScore){
                        continue;
                    }

                    dp[cnt+1][nextIndex] = nextScore;

                    q.add(nextIndex);

                }

            }
            cnt++;

        }

        for(int i=2;i<=M;i++){
            result = Integer.max(result,dp[i][N]);
        }

        System.out.println(result);


    }

    public static class Node{
        int index;
        int score;

        public Node(int index, int score) {
            this.index = index;
            this.score = score;
        }
    }
}