백준 16928 - 뱀과 사다리 게임

뱀이나 사다리를 만났을 때 , 이후에 이동해야하는 위치를 next배열을 두어 이동시켰다.

일반칸을 이동할때 , 뱀을 만났을때 , 사다리는 만났을 때를 따로 구분해서 처리하지 않고 next 배열을 통해 이동된 칸을 큐에 넣었다.

next[x] = y일 떄 , 

일반 칸 이면 y = x

뱀을 만났으면 y (내려간 칸)

사다리를 만났으면 y (올라간 칸)

이렇게 y를 큐에 넣어주어 bfs를 마저 진행하면 된다.

 

import java.io.*;
import java.util.*;
 
public class B16928 {
    static int[] next;
    static int[] count = new int[101];
    public static void bfs() {
        Queue<Integer> que = new LinkedList<>();
        boolean[] visit = new boolean[101];        
        que.add(1);
        visit[1] = true;
        while(!que.isEmpty()) {
            int tmp = que.poll();
            for(int i=1; i<= 6; i++) {
                if(tmp + i <= 100) {
                    int nx = tmp + i;
                    if(!visit[next[nx]]) {
                        que.add(next[nx]);
                        visit[next[nx]] = true;
                        count[next[nx]] = count[tmp] + 1;
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        next = new int[101];
        for(int i=1; i<=100; i++) {
            next[i] = i;
        }
 
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);
        for(int i=0 ; i<N+M ; i++) {
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            next[a] = b;
        }
        bfs();
        System.out.println(count[100]);
 
    }
}