[BOJ - JAVA] 16928 - 뱀과 사다리 게임 (BFS)

# 주소

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

16928번: 뱀과 사다리 게임

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Dice{
    int x;
    int cnt;
    Dice(int x, int cnt){
        this.x = x;
        this.cnt = cnt;
    }
}
class Main{
    static int n, m;
    static int[] hoop;
    static boolean[] visit;
    static Queue<Dice> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        visit = new boolean[101];
        hoop = new int[101];
        for (int i = 0; i < n + m; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            hoop[x] = y;
        }
        bfs();
    }
    static void bfs(){
        queue.offer(new Dice(1, 0));
        visit[1] = true;
        while(!queue.isEmpty()){
            Dice now = queue.poll();
            if(now.x == 100){
                System.out.println(now.cnt);
                System.exit(0);
            }
            for(int i = 1; i <= 6; i++){
                int nx = now.x + i;
                if(nx > 100)
                    continue;
                if(visit[nx])
                    continue;
                if(hoop[nx] > 0){
                    queue.offer(new Dice(hoop[nx], now.cnt + 1));
                    visit[hoop[nx]] = true;
                    continue;
                }
                queue.offer(new Dice(nx, now.cnt + 1));
                visit[nx] = true;
            }
        }
    }
}

1부터 100까지 10 x 10크기의 게임판이 있습니다.

1부터 출발하여 100에 도달하면 승리한다 했을 때 가장 빨리 도착할 수 있는 최소번의 횟수를 구하는 문제입니다.

문제를 잘 읽어보면 사다리를 밟으면 몇칸 위로 점핑할 수도 있고 뱀을 밟으면 다시 내려갈 수 있습니다.

그런데 이 둘을 따로 자료구조에 담아서 하기 보다는 그냥 지정한 인덱스로 이동하면 되기 때문에 int타입의 1차원 배열을 이용했습니다.

또한 BFS기법으로 푸시면 별 무리 없이 풀 수 있습니다.

감사합니다.