[BOJ-2157] 여행(JAVA)

[BOJ-2157] 여행(JAVA)

728x90

백준 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를 이용하여 풀 수 있다.

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

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

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

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

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

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

- 즉, 이 문제는 메모이제이션을 이용한 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 boards[] = new List[N+1]; for(int i=0;i<=N;i++){ boards[i]=new ArrayList<>(); } for(int i=0;i b){ continue; } boards[a].add(new Node(b,c)); } int result=0; Queue 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; } } }

from http://9327144.tistory.com/101 by ccl(A) rewrite - 2021-09-28 00:26:26