2157번 - 여행

2024-10-09

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약 :

•
N개의 도시 중 M개 이하의 도시를 여행한다.

•
반드시 1번에서 시작해 N번에서 끝나야 한다.

•
오름차순으로 이동한다.

•
기내식 점수의 총합이 최대가 되도록 한다.

문제 풀이 :

처음에 문제를 보고 bfs인가? dp인가? 약간 고민을 했다.

근데 문제 조건에서 오름차순으로 이동해야한다는 문장이 dp 같다는 생각이 들어서 dp로 풀어보고자 했다.

처음에는 3차원 배열을 만들어서 각 비행경로와 몇번째 이동인지를 저장하려고 했다.

근데 이렇게 해도 풀수는 있을 것 같은데

대충 아래와 같은 느낌으로 4 중첩 for 문이 나왔다.

근데 저것도 조건을 다 만족하지 못해서 대략 5~6 중첩 for 문이 나올 것 같다.

Java

for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                for (int l = 2; l <= m; l++) {
                    if (dp[i][j][l-1] != 0) {
                        for (int o = l; o <= n; o++) {
                            dp[i][o][l] = Math.max(dp[i][o][l], dp[i][j][l-1] + dp[j][o][l-1]);
                        }
                    }
                }
            }
        }

내가 구조를 잘못 짠 것같긴 한데.. 이런 방식으로는 못 풀 것 같다는 생각이었다.

근데 다른 풀이가 생각이 안나서 결국 다른 풀이를 참조했다.

이 문제는 dp와 bfs를 섞어서 푸는 것이었다.

dp를 2차원 배열로 현재 이동 횟수, 현재 도시 번호 로 저장을 한다.

그래서 현재 도시를 기준으로 이동할 수 있다면 해당 도시의 값을 최신화 해주는 것이다.

Java

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

public class Main {
    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());

        int[][] arr = new int[n + 1][n + 1];
        int[][] dp = new int[m + 1][n + 1];

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

            arr[a][b] = Math.max(arr[a][b], c);
        }

        Queue<Integer> q = new LinkedList<>();
        q.offer(1); //1번 도시부터 시작
        int cnt = 1; //현재 이동 횟수

        while (!q.isEmpty() && cnt<m) { //갈수있는 경로가 없거나, 이동 횟수를 초과할 때까지
            int size = q.size(); //현재 이동할 수 있는 경로

            while (size-- > 0) { 
                int now = q.poll();
                for (int i = now; i <= n; i++) {
                    if (arr[now][i] != 0) { //다음 경로가 존재하면 최신화
                        if (dp[cnt + 1][i] < dp[cnt][now] + arr[now][i]) {
                            dp[cnt+1][i] = dp[cnt][now] + arr[now][i];
                            q.offer(i);
                        }
                    }
                }
            }
            cnt++; //이동횟수 ++
        }

        int ans = 0;
        for (int i = 1; i <= m; i++) {
            ans = Math.max(ans, dp[i][n]);
        }

        System.out.println(ans);
    }
}