Java

[백준 2157] 여행 (JAVA)

iheeeee6-6 2023. 7. 11. 11:10
728x90

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

 

2157번: 여행

첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1

www.acmicpc.net

 

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);
	}
	
}

'Java' 카테고리의 다른 글

[백준 2228] 구간 나누기 (JAVA)  (0) 2023.07.12
[백준 1947] 선물 전달 (JAVA)  (0) 2023.07.11
[백준 1398] 동전 문제 (JAVA)  (0) 2023.06.27
[백준 17609] 회문 (JAVA)  (0) 2023.06.21
[백준 2258] 정육점 (JAVA)  (0) 2023.06.20