[JAVA] 백준 - 뱀과 사다리 게임 (BFS)

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

뱀으로 가면 무조건 손해라고 생각했지만 아니다.

 

만약 아래처럼 테스트 케이스를 주어진다고 해보자.

 

# 뱀을 타야만 최단거리를 만드는 테스트 케이스

2 1

2 50

49 100

51 48

 

 

1. 1을 던져서 2번으로 간 다음 사다리를 타고 50으로 간다.

2. 1을 던져서 51번으로 간 다음 뱀을 타고 48로 간다.

3. 1을 던져서 49번으로 간 다음 사다리를 타고 100번으로 간다.

 

 

답) 3

 

# 한 번 방문한 자리를 다시 방문 했을 때 최단거리를 만드는 경우의 수가 있는가??

방문 체크 배열을 만들기 전에 반드시 체크해봐야하는 질문이다.

 

현재 자리의 번호가 A 라고 가정한다.

 

" A - ( X - X - X - X - ... ) - A - B - 도착지 "  

 

위의 경우 A 에서 시작하여 다시 A로 돌아온다음 B위치로 가서 도착지로 가는 경로다.

직관적으로 봤을 때 다시 돌아와서 도착지로 갔을 때 최단거리를 갱신하는 경우는 불가능하다.

 

따라서 방문 체크 배열로 만들어 해당 번호를 방문하면 다시는 방문하지 않아도 된다.

 

 

<자바 코드>

import java.util.LinkedList;
import java.util.*;
class Main{

    static int n;
    static int m;
    static int answer = Integer.MAX_VALUE;
    static HashMap<Integer,Integer> ladder = new HashMap<>();
    static HashMap<Integer,Integer> snake = new HashMap<>();
    static boolean[] visited = new boolean[101];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
         n = sc.nextInt();
         m = sc.nextInt();
         int a,b;
         for(int i=0;i<n;i++){
             a = sc.nextInt();
             b = sc.nextInt();
             ladder.put(a,b);
         }
         for(int i=0;i<m;i++){
             a = sc.nextInt();
             b = sc.nextInt();
             snake.put(a,b);
         }

         Queue<Pair> q = new LinkedList<>();
         Pair start = new Pair(1,0);
         q.add(start);
         visited[1] = true;

         while(!q.isEmpty()){
             Pair p = q.poll();

             if(p.x == 100){
                 if(p.cnt < answer){
                     answer =p.cnt;
                 }
             }

             for(int i=1;i<=6;i++){
                 int nx = p.x + i;

                 if(nx<=100 && visited[nx]==false){
                     visited[nx] = true;
                     if(ladder.containsKey(nx)){
                         nx = ladder.get(nx);
                         visited[nx] = true;
                     }
                     if(snake.containsKey(nx)){
                         nx = snake.get(nx);
                         visited[nx] = true;
                     }
                     q.add(new Pair(nx,p.cnt+1));
                 }
             }
         }
        System.out.println(answer);
    }

    static class Pair{
        int x,cnt;

        public Pair(int x,int cnt){
            this.x = x;
            this.cnt = cnt;
        }
    }



}