오늘의 지식 채우기

알고리즘/Java

백준 알고리즘 2157번: 여행

두넌 2024. 6. 8.

문제 정보

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

 

 

문제 파악

문제 조건

1 <= N <= 300

2 <= M <= N

1 <= K <= 100,000

(N: 도시의 수, M: 방문할 최대 도시의 수, K: 개설된 항공로의 개수)

 

문제 내용

1번 도시부터 N번 도시까지 최대 M개의 도시를 방문하고, 가중치(기내식의 점수)의 합의 최대를 출력해야 한다

 

 

풀이

생각했던 내용

처음에 DFS로 문제를 풀이해 보았다 (시간 초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int M;
    private static int N;
    private static int result;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 도시의 수 (1-N번 도시)
        N = Integer.parseInt(st.nextToken());
        // 방문할 도시의 수 M개 (이하)
        M = Integer.parseInt(st.nextToken());
        // 개설된 항공로의 개수
        int K = Integer.parseInt(st.nextToken());

        // 동 -> 서 방향으로만, 도시 번호가 증가하는 순서대로만 이동

        map = new int[N + 1][N + 1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(map[i], -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());

            // 같은 도시 쌍 사이에 항로가 여러 개 있을 수도 있으므로 기내식의 점수가 최대인 항로를 입력받자
            map[a][b] = Math.max(map[a][b], c);
        }

        solve(1, 0, 1);
        System.out.println(result);
    }

    private static void solve(int current, int sum, int count) {
        if (current == N) {
            result = Math.max(result, sum);
            return;
        }

        if (count >= M) {
            return;
        }

        for (int i = current + 1; i <= N; i++) {
            if (map[current][i] != -1) {
                solve(i, sum + map[current][i], count + 1);
            }
        }
    }
}

무작정 모든 경우를 판별하기에는 어려움이 있었다. 시간 복잡도는 다음과 같다

 

  • solve 메소드는 DFS를 사용하여 경로를 탐색합니다. 최대 M개의 도시를 방문할 수 있으므로, 재귀 호출의 깊이는 최대 M입니다.
  • 각 호출에서 다음 도시를 선택하는 경우의 수는 최대 N - 현재 도시입니다. 이는 최악의 경우 O(N)이 될 수 있습니다.
  • 재귀 호출의 경우의 수를 고려하면, 모든 가능한 경로를 탐색하는 시간복잡도는 대략 O(N^M)이 됩니다.

 

 

풀이한 내용

갈 수 있는 항공편에 대한 입력을 받고, 반드시 1번 도시에서 출발해야 하며 도시들을 경유해갈 수 있기 때문에 정렬이 있어야 한다고 판단하였다.

// 동 -> 서 방향으로만, 도시 번호가 증가하는 순서대로만 이동
int[][] flight = new int[K][3];

for (int i = 0; i < K; i++) {
    st = new StringTokenizer(br.readLine());
    flight[i][0] = Integer.parseInt(st.nextToken());
    flight[i][1] = Integer.parseInt(st.nextToken());
    flight[i][2] = Integer.parseInt(st.nextToken());
}

Arrays.sort(flight, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0]) {
            return o1[1] - o2[1];
        }
        return o1[0] - o2[0];
    }
});

따라서, 출발지를 기준으로 정렬하되 같으면 도착지가 빠른 순으로 오름차순 정렬되도록 코드를 작성하였다

 

// 1부터 N까지 M개의 도시를 지났음
int[][] dp = new int[N + 1][M + 1];
for (int i = 2; i <= N; i++) {
    Arrays.fill(dp[i], -1);
}

이후 DP 배열을 선언하였다.

DP[i][j] 의 의미는 1번 도시에서 i번 도시까지 j개의 도시를 방문하여 갈 수 있는 가중치 합의 최대 이다.

i=2부터 N까지의 경로는 아직 모르는 상태이므로, 갈수 없다는 의미로 -1로 채워주었다.

 

for (int i = 0; i < K; i++) {
    int start = flight[i][0];
    int end = flight[i][1];
    int score = flight[i][2];

    if (start >= end) {
        continue;
    }
    for (int m = 2; m <= M; m++) {
        if (dp[start][m - 1] == -1) {
            continue;
        }
        dp[end][m] = Math.max(dp[end][m], dp[start][m - 1] + score);
    }
}

반드시 동쪽으로만 움직여야 하므로(숫자가 커지는 방향으로) start >= end 일 수는 없기에 해당 경우의 입력에 대해서는 어떠한 동작도 하지 않도록 구현하였다

또한, 처음 도시인 1부터 시작하기 때문에 다음 도시의 경우 최소 2개의 도시를 방문한 것이기 때문에 m=2 부터 for loop 를 돌려 주었다.

 

만약 dp[start][m-1] (이전 도시에 방문할 수 있는 경우) 가 -1인 경우, 현재 위치 또한 방문할 수 없기 때문에 continue를 진행하였고

아닌 경우라면 현재의 값과 이전 도시에서 현재 도시로 날아올 때의 가중치를 더한 값을 비교하는 형식으로 최대값을 찾아나갔다

 

int result = 0;
for (int i = 2; i <= M; i++) {
    result = Math.max(result, dp[N][i]);
}

결과적으로 N번째 도시에는 방문이 이루어져야 하기 때문에, N번째 도시까지의 최소 방문 도시 2개부터 최대 M개까지 중 최대값을 구하면 답을 도출할 수 있다

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
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());

        // 도시의 수 (1-N번 도시)
        int N = Integer.parseInt(st.nextToken());
        // 방문할 도시의 수 M개 (이하)
        int M = Integer.parseInt(st.nextToken());
        // 개설된 항공로의 개수
        int K = Integer.parseInt(st.nextToken());

        // 동 -> 서 방향으로만, 도시 번호가 증가하는 순서대로만 이동
        int[][] flight = new int[K][3];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            flight[i][0] = Integer.parseInt(st.nextToken());
            flight[i][1] = Integer.parseInt(st.nextToken());
            flight[i][2] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(flight, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        // 1부터 N까지 M개의 도시를 지났음
        int[][] dp = new int[N + 1][M + 1];
        for (int i = 2; i <= N; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 0; i < K; i++) {
            int start = flight[i][0];
            int end = flight[i][1];
            int score = flight[i][2];

            if (start >= end) {
                continue;
            }
            for (int m = 2; m <= M; m++) {
                if (dp[start][m - 1] == -1) {
                    continue;
                }
                dp[end][m] = Math.max(dp[end][m], dp[start][m - 1] + score);
            }
        }

        int result = 0;
        for (int i = 1; i <= M; i++) {
            result = Math.max(result, dp[N][i]);
        }

        System.out.println(result);
    }
}

 

 

Source Code on GitHub

GitHub에서 소스코드 보기

 

 

저작자표시

댓글

티스토리툴바