20293번 - 연료가 부족해

2025-02-17

#JAVA#백준

문제 링크

문제 풀이 시간 : 2시간

문제 풀이 :

처음에는 간단한 dfs 문제라고 생각하고 dfs로 코드를 짰다

초기 위치에서 가지고 있는 연료(have)와 필요한 연료(need)를 둘 다 0으로 초기화하고,

dfs로 탐색하면서 각 위치에 따라 have가 있다면 다음 위치로 이동하며 have를 1 차감하고,

have가 0이라면 need를 1 증가하며 이동했다.

Java

public static void dfs(int x, int y, int have, int need) { //x좌표, y좌표, 가지고 있는 연료, 필요한 연료
        if (x == r && y == c) { //목적지에서 필요한 연료 계산
            min = Math.min(need, min);
            return;
        }
        if (arr[x][y] != 0) { //현재 위치가 충전소라면 연료 충전
            have += arr[x][y];
        }
        for (int i = 0; i < 2; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];

            if (check(dx, dy)) { //지도를 벗어나지 않는지
                return;
            }

            if (have > 0) { //연료가 있다면
                dfs(dx, dy, have - 1, need); //연료 차감
            } else { //연료가 없으며
                dfs(dx, dy, have, need + 1); //필요한 연료 증가
            }
        }
    }

그리고 마지막 r,c 위치에서 need의 수를 출력하면 최초에 필요한 연료의 크기를 구할 수 있다.

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;

class Main{
    public static int r,c,n;
    public static int[][] arr;

    public static int[][] dir = {{0, 1}, {1, 0}};
    public static int min = Integer.MAX_VALUE;

    public static boolean check(int a, int b) {
        return a < 1 || a > r || b < 1 || b > c;
    }

    public static void dfs(int x, int y, int have, int need) { //x좌표, y좌표, 가지고 있는 연료, 필요한 연료
        if (x == r && y == c) { //목적지에서 필요한 연료 계산
            min = Math.min(need, min);
            return;
        }
        if (arr[x][y] != 0) { //현재 위치가 충전소라면 연료 충전
            have += arr[x][y];
        }
        for (int i = 0; i < 2; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];

            if (check(dx, dy)) { //지도를 벗어나지 않는지
                return;
            }

            if (have > 0) { //연료가 있다면
                dfs(dx, dy, have - 1, need); //연료 차감
            } else { //연료가 없으며
                dfs(dx, dy, have, need + 1); //필요한 연료 증가
            }
        }
    }

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(br.readLine());

        arr = new int[r + 2][c + 2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

        dfs(1, 1, 0, 0);
        System.out.println(min);
    }
}

하지만 이렇게 하면 1%에서 시간초과가 나온다.

아무리 생각해도 방법을 모르겠어서

결국 다른사람들의 코드를 참고했다.

이 문제는 dp와 이분탐색을 사용해서 풀어야하는 문제이다.

•
이동은 아래, 오른쪽 두가지만 존재하기 때문에 1,1에서 r,c로 이동할 때 필요한 최대 연료는 r+c-2이다.

•
초기 연료 f를 1,1과 r+c-2 사이에서 이분탐색하며 탐색한다.

•
find(f)를 이용해서 f라는 연료를 통해 1,1에서 r,c로 이동할 수 있는지 확인한다.

Java

int s = 1, e = r + c - 2;
while (s <= e) {
    int mid = (s + e) / 2;
    
    if (find(mid)) {
        e = mid - 1;
    } else {
        s = mid + 1;
    }
}

•
dp배열에는 i번째 위치에서의 연료의 양이 저장되어 있다.

•
각 위치는 시작위치, 충전소의 위치, 도착위치가 있다. (즉, dp 배열의 크기는 n+2)

•
그 후 각 위치에서 이전 위치에서 현재 위치로 이동할 수 있는지 확인한다.

Java

public static boolean find(int f) {
    int[] dp = new int[n + 2];
    
    Arrays.fill(dp, -1);
    dp[0] = f; //초기 위치 연료량 설정
    fuels[0][2] = f; //초기 위치 연료량 설정
    
    for (int i = 1; i < n + 2; i++) {
        for (int j = 0; j < i; j++) {
            if (fuels[j][0] > fuels[i][0] || fuels[j][1] > fuels[i][1]) { //j위치에서 i위치로 이동할 수 없음
                continue;
            }
            
            if (dp[j] < dist(j, i)) { //이동거리보다 연료량이 적음
                continue;
            }
            
            //dp배열 최대크기로 설정
            dp[i] = Math.max(dp[i], dp[j] - dist(j, i) + fuels[i][2]); 
        }
    }
    
    //도착점의 dp 배열 값이 0이상이라면 true 반환
    return dp[n + 1] >= 0;
}

전체 코드

Java

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

class Main {
    public static int r, c, n;
    public static int[][] fuels;

    public static int dist(int i, int j) {
        return fuels[j][0] + fuels[j][1] - fuels[i][0] - fuels[i][1];
    }

    public static boolean find(int f) {
        int[] dp = new int[n + 2];

        Arrays.fill(dp, -1);
        dp[0] = f;
        fuels[0][2] = f;

        for (int i = 1; i < n + 2; i++) {
            for (int j = 0; j < i; j++) {
                if (fuels[j][0] > fuels[i][0] || fuels[j][1] > fuels[i][1]) {
                    continue;
                }

                if (dp[j] < dist(j, i)) {
                    continue;
                }

                dp[i] = Math.max(dp[i], dp[j] - dist(j, i) + fuels[i][2]);
            }
        }

        return dp[n + 1] >= 0;
    }

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(br.readLine());

        fuels = new int[n + 2][3];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            fuels[i][0] = Integer.parseInt(st.nextToken());
            fuels[i][1] = Integer.parseInt(st.nextToken());
            fuels[i][2] = Integer.parseInt(st.nextToken());
        }
        fuels[0] = new int[]{1, 1, 0};
        fuels[n + 1] = new int[]{r, c, 0};

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

        int s = 1, e = r + c - 2;

        while (s <= e) {
            int mid = (s + e) / 2;

            if (find(mid)) {
                e = mid - 1;
            } else
                s = mid + 1;
        }

        System.out.println(s);
    }
}

너무 당연하게 dfs로 생각했지만 dp와 이분탐색을 섞어서 푸는 색다른 문제였다.