[Algorithm] Snakes and Ladders: The Quickest Way Up

Snakes and Ladders: The Quickest Way Up

---

[Problem]

1번 바닥에서 시작하여 100번 바닥에 도착하기 위해 최소한으로 몇 번을 이동해야 하는가 ? 

조건 1. 주사위의 수는 원하는데로 나온다고 가정한다. 

조건 2. 현재 위치에서 100을 넘어가게 되면 이동하지 않고 현재 자리에 가만히 있는다. 

조건 3. 사다리 칸에 도착하면 밑에서 올라갈 수만 있고, 뱀을 만나면 머리에서 꼬리로만 이동이 가능하다.

조건 4. 한 게임 칸은 사다리의 끝, 뱀의 머리가 동시에 될 수 없다. 

[Constraints]

게임판은 10x10이며 도착지점의 번호는 100이다.

총 테스트 케이스 T : 1<= T <= 10 

뱀의 수 : 1<= N <= 15

사다리의 수 : 1<= M <= 15

각 테스트 케이스 마다 

첫 번째 줄에는 사다리의 갯수 N이 주어진다.

이후 각 줄 마다 사다리의 시작 지점과 끝 지점이 주어진다. 

그 다음 줄에는 뱀의 갯수 M이 주어진다.

 이후 각 줄 마다 뱀의 시작지점과 끝 지점이 주어진다. 

[Solve]

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

    public static int[][] G = null;

    public static int[] cache = null;

    public static boolean[][] visited = null;

    public static int maxEndPoint = 0;

    public static int minMoves = Integer.MAX_VALUE;

    

    public static void main(String[] args) {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        Scanner scanner = new Scanner(System.in);

        

        int T = scanner.nextInt();

        

        for(int i=0; i<T; i++){

            maxEndPoint = 0;

            cache = new int[101];

            G = new int[101][101];

            visited = new boolean[101][101];

            

            int N = scanner.nextInt();

            

            int s = 0;

            int e = 0;

            for(int t=1;t<=99;t++){

                if(100-t>=6){

                    for(int k=1;k<=6;k++)

                        G[t][t+k]=1;

                }

                else{

                    for(int k=1; k<=(100-t);k++)

                        G[t][t+k]=1;

                }

            }

            

            // ladder

            for(int n=0; n<N;n++){

                s = scanner.nextInt();

                e = scanner.nextInt();

                

                if(maxEndPoint<e)

                    maxEndPoint = e;

                G[s][e] = 2;

            }

            

            // snake

            int M = scanner.nextInt();

            for(int m=0; m<M; m++){

                s = scanner.nextInt();

                e = scanner.nextInt();

                

                if(maxEndPoint<e)

                    maxEndPoint = e;

                G[s][e] = 2;

            }

            //traverse(1,0,0);

            //BFS(1);

            

            int ret = BFS(1);

            if(ret == Integer.MAX_VALUE)

                System.out.println("-1");

            else

                System.out.println(ret);

        }// end testcases

        

    }// end main

    

    public static int BFS(int S){

        

        boolean[] visited = new boolean[101];

        int[] distance = new int[101];

        

        //거리 최대값으로 초기화 

        

        for(int i=0;i<101;i++)

            distance[i] = Integer.MAX_VALUE;

        //시작점 거리 0 

        distance[1]=0;

        

        LinkedList<Integer> queue = new LinkedList<Integer>();

        queue.add(S);

        

        while(queue.size()!=0){

            

            int start = queue.poll(); // get first element 

            for(int idx=1;idx<=100;idx++){

                if(G[start][idx]==1 && !visited[idx]){

                    

                    // 지금 node와 인접한 node들 추가 

                    queue.add(idx);

                    visited[idx] = true;

                    

                    // start와 idx는 인접해 있으므로 거리는 1차이 

                    if(distance[idx]>distance[start]+1)

                        distance[idx] = distance[start]+1;

                }

                // ladder, snake의 경우 node의 이동은 있지만, 주사위횟수의 증감은 없다.

                // 즉, 건너넘어오기 전의 node의 distance를 그대로 물려받는다. 

                else if(G[start][idx] ==2 && !visited[idx]){

                    queue.add(idx);

                    visited[idx]=true;

                    distance[idx] = distance[start];

                }

            }// end for 

        }// end while 

        

        return distance[100];

    }// end method