[JAVA] 백준 16928 - 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

 

 

 

 

처음에 순수 DP로 풀었으나 실패해서

 

BFS + DP(??) 를 활용해서풀었다

 

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

public class Main {
    public static int N;
    public static int ans = Integer.MAX_VALUE;
    public static int[] ladders = new int[101];
    public static int[] dp = new int[101];
    public static void main(String[] args) throws Exception {
        Arrays.fill(dp, Integer.MAX_VALUE);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int sum = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());

        for(int i = 0 ; i < sum ; i++){
            st = new StringTokenizer(br.readLine());
            ladders[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
         }
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(1,0));



        while(!queue.isEmpty()){
//            System.out.println(queue);

            Point p =  queue.poll();

            int candidate_2 = ladders[p.pos];
            if(candidate_2 != 0){ //사다리 탈게 있다면
                if(ladders[candidate_2] != p.pos && dp[candidate_2] > p.count){ //사이클이 없어야 추가
                    queue.add(new Point(candidate_2, p.count));
                    dp[candidate_2] = p.count;
                }
            }else{ //사다리 탈게 없다면

                for(int i = 1 ; i <= 6 ; i++){
                    int candidate_1 = p.pos + i;
                    if(candidate_1 <= 100 && dp[candidate_1] > p.count + 1){
                        queue.add(new Point(candidate_1, p.count + 1));
                        dp[candidate_1] = Math.min(dp[candidate_1], p.count+ 1);
                    }
                }
            }
        }
        System.out.println(dp[100]);
    }

}

class Point {
    int pos;
    int count;

    public Point(int pos, int count) {
        this.pos = pos;
        this.count = count;
    }
    @Override
    public String toString(){
        return pos + "," + count;
    }
}

 

사다리(뱀)을 탈게있다면 queue에 도착점을 집어넣는다. 하지만 죄다 넣게된다면 무한루프를 빠져나오지 못하는 경우가 생길수있으므로, dp[]를 갱신해야만 queue에 집어넣을수 있게 if문으로 처리를 해주었다.

 

사다리(뱀)를 탈게 없다면 현재 지점에서 1더한것, 2더한것, 3더한것, 4더한것, 5더한것, 6더한것을 Queue에 Add한다.

하지만 죄다 넣게되면 무한루프가 발생하므로, dp[]배열을 보고 최솟값을 갱신해야만 queue에 집어넣게 구현하였다.