백준 16928번 뱀과 사다리 게임 JAVA

링크텍스트

설명

사다리와 뱀이 있는 칸은 배열에 값을 저장해 위치를 표시했고 BFS를 통해 주사위를 굴리는 횟수의 최솟값을 구했다. 큐에는 현재 위치와 주사위를 굴린 횟수를 저장했고 이미 방문한 칸은 체크하여 다시 방문하지 않도록 했다.

코드

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

class Main {
        static int n,m;
        static int [] arr = new int[101];
        static boolean [] check = new boolean[101];
        static int min = 0;
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    
	    n = Integer.parseInt(st.nextToken());
	    m = Integer.parseInt(st.nextToken());
	    
	    for(int i=0;i<n;i++){
	        st = new StringTokenizer(br.readLine());
	        int x = Integer.parseInt(st.nextToken());
	        int y = Integer.parseInt(st.nextToken());
	        
	        arr[x] = y;
	    }
	    
	    for(int i=0;i<m;i++){
	        st = new StringTokenizer(br.readLine());
	        int u = Integer.parseInt(st.nextToken());
	        int v = Integer.parseInt(st.nextToken());
	        
	        arr[u] = v;
	    }
	    
	    bfs(1);

        System.out.println(check[100] ? min:-1);
	}
	
	public static void bfs(int n){
	    Queue<int []> q = new LinkedList<>();
        q.offer(new int[]{1,0});
        check[n] = true;

        while (!q.isEmpty()) {
            int [] current = q.poll();
            int position = current[0];
            int count = current[1];

            if(position==100){
                min = count;
                return;
            }

            for(int i=1;i<=6;i++){
                int next = position+i;

                if(next>100) continue;

                if(arr[next]!=0){
                    next = arr[next];
                }

                if(!check[next]){
                    check[next] = true;
                    q.offer(new int[]{next,count+1});
                }
            }
        } 
	}
}