[백준] 2157번 여행 (Java)

0. 출처

백준 2157번 문제입니다.

 

1. 문제

N개의 도시가 동쪽에서 서쪽으로 순서대로 위치해 있다. 제일 동쪽에 있는 도시는 1번 도시이며, 제일 서쪽에 있는 도시는 N번 도시이다. 당신은 이와 같은 도시 중에서 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝나야 한다. 물론 이 두 도시도 M개의 도시에 포함된다. 당신은 시차에 매우 민감하기 때문에, 한 번 서쪽으로 이동했다가 다시 동쪽으로 이동하면 몸이 대단히 아프다. 그래서 당신은 계속 서쪽으로만, 즉 도시 번호가 증가하는 순서대로만 이동하기로 하였다.

한편, 모든 도시에서 다른 모든 도시로 이동할 수 있는 건 아니다. 각각의 도시에서 다른 도시로 이동할 때에는 비행기를 타고 이동해야 하는데, 때로는 비행 항로가 개설되지 않았을 수도 있다. 또한 당신은 비행기를 아무렇게나 타려는 것이 아니라, 최대한 맛있는 기내식만 먹으면서 이동하려 한다(사실 이게 여행의 목적이다)

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

(1) 입력

첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 10,000)가 주어진다. 이는 a번 도시에서 b번 도시로 이동하는 항로가 있고, 서비스되는 기내식의 점수가 c점이라는 의미이다. 서쪽에서 동쪽으로 이동하는 항로가 입력될 수도 있고, 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있지만, 날아다니다 다시 원래 도시로 돌아오는 a=b 와 같은 입력은 없다.

(2) 출력

첫째 줄에 기내식 점수의 총 합의 최댓값을 출력한다.

 

2. 문제 풀이

(1) 문제 풀이 방법

저는 처음에 비행기 경로가 그래프 형식이니 그래프 탐색을 통해 문제를 풀었습니다. 그런데 메모리 초과가 나오더라구요.. 그 이유는 바로 "중복"이 많기 때문입니다!

 

예를 들어 1번 도시에서 5번 도시까지 3번만에 갈 때 기내식의 최댓값이 20이라면? 도시를 3번 이상 거치는 경로는 필요없고, 기내식 20 이하의 경로도 필요가 없는 것이죠!

 

그래서 dp[i][j] = k 를 <i번만에 j 도시에 도착했을 때 기내식 합의 최댓값> 로 정의해서 dp를 사용했습니다.

 

(2) 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    static int[][] dp;
    
    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 K = Integer.parseInt(st.nextToken());

        dp = new int[M+1][N+1];
        List<City>[] airplanes = new List[N+1];
        for(int i=1; i<N+1; i++) {
            airplanes[i] = new ArrayList<>();
        }
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if(a>b) continue; // 동쪽으로 이동하는 경로는 필요없음
            airplanes[a].add(new City(b, c));
        }

        int answer = 0;
        int count = 1;
        
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        while(!q.isEmpty() && count < M) {
            int size = q.size();
            while(size-->0) { // count마다 갈 수 있는 경로 dp 계산
                int now = q.poll();
                for(City c: airplanes[now]) {
                    int next = c.number;
                    int nextCount = dp[count][now]+c.value;
                    
                    if(dp[count+1][next]>=nextCount) continue;
                    
                    dp[count+1][next] = nextCount;
                    q.add(next);
                }
            }
            count++;
        }
        for(int i=2; i<=M; i++) {
            answer = Math.max(answer, dp[i][N]);
        }

        System.out.println(answer);
        br.close();
    }
    
    static class City {
        int number;
        int value;
        
        public City(int number, int value) {
            this.number = number;
            this.value = value;
        }
    }
}

 

(3) 결과