[백준 2157] 여행 (JAVA)

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

2157번: 여행

 

DP 문제로 처음에 생각해내기 어려웠다..

 

풀이

1. 리스트 배열을 만들어서 배열의 인덱스는 출발지, 리스트에는 도착지와 점수를 넣는다. ( 만일, 도착지가 출발지보다 작은 수라면 동쪽이동이기 때문에 스킵!)

2. dp 이차원배열을 생성하여 "new int[몇번째로 방문한 것인지=> m+1][도착지 번호=>n+1] = 점수" 를 저장할 것이다. 

3. 큐를 생성하여 출발지를 넣는다.

4. 맨 처음의 출발지는 1이고, 첫번째로 방문한 곳이기에 count=1

5. 큐에 담아 있는 곳들은 모두 같은 방문 번호를 같기에 size를 추출하여 포문을 돌린다.

6. 만일, 출발지로부터 온 점수보다 이미 dp에 저장되어 있는 점수가 더 높을 경우에는 스킵한다.

7. 그렇지 않다면, dp에 해당 값을 저장하고 큐에 해당 도착지를 넣는다.

8. dp[2~m번째로 방문][n]의 최대값을 찾아 출력한다! 끝!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n, m, k;
	static int result=0;
	
	static class Node{
		int idx;
		int point;
		Node(int idx,int point){
			this.idx=idx;
			this.point=point;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		ArrayList<Node>[] map= new ArrayList[n+1];
		for(int i=1;i<=n;i++) {
			map[i]= new ArrayList<>();
		}
		
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			if(e<s) continue;
			map[s].add(new Node(e,p));
		}

		int[][] dp = new int[m+1][n+1];
		Queue<Integer> q = new LinkedList<>();
		q.add(1);
		int count=1;
		while(!q.isEmpty()&&count<m) {
			int size = q.size();
			for(int z=0;z<size;z++) {
				int idx=q.poll();
				for(Node node:map[idx]) {
					if(dp[count][idx]+node.point<=dp[count+1][node.idx]) continue;
					dp[count+1][node.idx]=dp[count][idx]+node.point;
					q.add(node.idx);
				}
			}
			
			count++;
		}
		
		for(int i=2;i<=m;i++) {
			result=Math.max(result, dp[i][n]);
		}
		
		System.out.println(result);
	}
	
}