[백준 33677 / Silver1] 푸앙이와 콩나무 - Java(자바)

작성자 : 고유진
문제 링크 : https://www.acmicpc.net/problem/33677

❓문제 설명

🎁 문제 풀이

물을 하루에 한 번씩 주어야 하고 콩나무는 3가지의 규칙을 따라 자람
1. 콩나무 길이 + 1
2. 콩나무 길이 * 3
3. 콩나무 길이 ^ 2
이렇게 길어지며 주어진 N에 도달하는 최소 날짜와 최소 물 소비량을 구하는 문제
즉, 0부터 N까지 가는 가장 빠른(=최소 일수) 경로를 찾는 것이므로 BFS를 활용
갈 수 있는 3가지 규칙 연산을 차례차례 큐에 넣으며 가장 먼저 도달하는 경우 = 최소 날짜
그래서 boolean을 활용하여 visited를 사용하려다 동일한 날짜에 도달할 경우 물 소비가 더 적은 날짜를 선택해야 했기에 조건을 활용하는 방식으로 코드를 수정
3가지 규칙 연산에서 각각 이전 날짜의 경로 혹은 이전 연산의 경로를 비교하여 갱신하도록 함
1. 새로운 경로가 더 빨리 도착한 경우 -> 갱신
2. 같은 날짜에 도착하긴 했는데, 현재 경로가 물을 덜 썼다면 갱신

🖥️ 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        if (N == 0) {
            bw.write("0 0\n");
            bw.flush();
            return;
        }

        int[] days = new int[N + 1];     
        int[] water = new int[N + 1];    

        Arrays.fill(days, Integer.MAX_VALUE);
        Arrays.fill(water, Integer.MAX_VALUE);

        days[0] = 0;
        water[0] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);

        while (!queue.isEmpty()) {
            int cur = queue.poll(); 
            int nextDay = days[cur] + 1; 

            // +1
            int next = cur + 1; 
            if (next <= N) {
                int newWater = water[cur] + 1;
                if (days[next] > nextDay) { 
                    days[next] = nextDay;
                    water[next] = newWater;
                    queue.add(next);
                } else if (days[next] == nextDay && water[next] > newWater) { 
                    water[next] = newWater;
                    queue.add(next);
                }
            }

            // *3
            next = cur * 3;
            if (cur > 0 && next <= N) {
                int newWater = water[cur] + 3;
                if (days[next] > nextDay) {
                    days[next] = nextDay;
                    water[next] = newWater;
                    queue.add(next);
                } else if (days[next] == nextDay && water[next] > newWater) {
                    water[next] = newWater;
                    queue.add(next);
                }
            }

            // ^2
            long sq = (long) cur * cur;
            if (cur > 1 && sq <= N) {
                next = (int) sq;
                int newWater = water[cur] + 5;
                if (days[next] > nextDay) {
                    days[next] = nextDay;
                    water[next] = newWater;
                    queue.add(next);
                } else if (days[next] == nextDay && water[next] > newWater) {
                    water[next] = newWater;
                    queue.add(next);
                }
            }
        }

        bw.write(days[N] + " " + water[N] + "\n");
        bw.flush();
    }
}