자바(백준) 21317 징검다리 건너기

오답 노트 & 새로 알게 된 점

문제를 읽으면서 숨바꼭질 문제와 비슷한 느낌을 받았다.

 

bfs를 이용하여 N에 도달할 때 에너지 최솟값을 구해주면 된다.

 

다만 풀면서 실수한 점이 작은 점프, 큰 점프, 매우 큰 점프를 하면서

n의 값 또한 더 증가된다.

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, k, ans = Integer.MAX_VALUE;
    static int jump[][];
 
    static class Stone{
        int n, sum;
        boolean flag;
 
        public Stone(int n, int sum, boolean flag) {
            this.n = n;
            this.sum = sum;
            this.flag = flag;
        }
    }
    public static void main(String[] args) throws IOException {
        input();
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
 
        jump = new int[N + 1][2];
 
        for(int i = 1; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int small = atoi(st.nextToken());
            int big = atoi(st.nextToken());
            jump[i][0] = small;
            jump[i][1] = big;
        }
 
        k = atoi(br.readLine());
 
        bfs();
    }
 
    static void bfs() {
        Queue<Stone> q = new ArrayDeque<>();
        q.offer(new Stone(1, 0, false));
 
        while (!q.isEmpty()) {
            Stone s = q.poll();
 
            if(s.n > N) continue;
            
            if(s.n == N){
                ans = Math.min(ans, s.sum);
                continue;
            }
 
 
            q.offer(new Stone(s.n + 2, s.sum + jump[s.n][1], s.flag));
            q.offer(new Stone(s.n + 1, s.sum + jump[s.n][0], s.flag));
 
            if(s.flag == false) {
                q.offer(new Stone(s.n + 3, s.sum + k, true));
            }
        }
 
        System.out.println(ans);
    }
}