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

백준 16928번 문제 - 뱀과 사다리 게임

16928번: 뱀과 사다리 게임

---

문제 분석 

 

 

• 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다.
• 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다.
  • 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.
• 플레이어는 주사위를 굴려 나온 수만큼 이동
  • 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다.
  • 도착한 칸이 사다리면, 사다리를 타고 위로 이동
  • 뱀이 있는 칸에 도착하면, 뱀을 따라서 아래로 이동
• 게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.
  이 때, 100번 칸에 도착하기 위해 주사위를 굴려야하는 횟수의 최솟값을 출력해라.

---

 

해결 포인트

 

• BFS 사용
• 사다리, 뱀 이동을 Map에 저장
• count를 저장하는 배열에 각 위치에 최소 횟수를 저장한다.
• 방문 체크한다
  • 사다리를 타거나, 뱀을 통해 이동할 경우 방문 확인 하지않고 무조건 이동한다.
• BFS 진행할 때 두개의 큐를 시용한다.
  • 다음 이동을 나타내는 큐(queue)와 사다리나 뱀으로 현재 바로 이동을 나타내는 큐(nextQueue)
  • 이유는 바로 이동을 나타내는 큐일 경우는 count를 증가시키기 전에 확인을 끝내야하기 때문이다.

 

---

 

코드

 

import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {
    public static HashMap<Integer, Integer> ladders, snakes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ladders = new HashMap<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            ladders.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        snakes = new HashMap<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            snakes.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        bw.write(BFS(N) + "\n");
        bw.flush();
        bw.close();
    }

    public static int BFS(int N) {
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> nextQueue = new LinkedList<>();
        boolean [] visit = new boolean[101];
        int [] counts = new int[101];

        queue.add(1);
        visit[1] = true;

        int count = 0;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            int nextQueueSize = 0;
            for (int i = 0; i < queueSize+nextQueueSize; i++) {

                int value;
                if(i < queueSize) value = queue.poll();
                else value = nextQueue.poll();

                if(ladders.containsKey(value)) {
                    int next = ladders.get(value);
                    counts[next] = count;
                    visit[next] = true;
                    nextQueue.add(next);
                    nextQueueSize++;

                    continue;
                }

                if(snakes.containsKey(value)) {
                    int next = snakes.get(value);
                    counts[next] = count;
                    visit[next] = true;
                    nextQueue.add(next);
                    nextQueueSize++;
                    continue;
                }

                for (int j = 1; j <= 6; j++) {
                    if(value + j <= 100 && !visit[value+j]) {
                        counts[value+j] = count+1;
                        visit[value+j] = true;
                        queue.add(value+j);
                    }
                }
            }

            count++;
        }
        return counts[100];
    }
}