[백준, Java] 16928번 : 뱀과 사다리 게임

🔗 문제 링크

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

😮 문제 해결 방법

주사위를 조작할 수 있다고 문제에서 제시했기 때문에 매 위치마다 1~6번까지의 주사위를 던진 후 위치를 담은 Node 객체에 다음 위치와 다음 거리(주사위 던진 개수)를 넣어 큐에 넣어주었다.

 

매 주사위 굴린 후의 위치에서는 뱀과 사다리가 있는 칸인지 먼저 확인한다.

 

뱀과 사다리가 있는 칸인 경우 주사위를 한번 굴린 것으로 뱀과 사다리를 탄 이후의 칸으로 이동이 가능하기 때문에 뱀과 사다리 탄 이후 칸 거리 배열에 현재까지 위치의 주사위 개수 + 1을 한 값을 넣어준다.

 

뱀과 사다리가 없는 칸인 경우 주사위 굴린 이후의 칸 거리 배열에 현재 까지의 주사위 개수 + 1 한 값을 넣어준다.

 

현재 큐의 칸이 100번째 칸이면 도착한 칸 이므로 100번째 거리배열을 리턴한다.

 

1. 사다리와 뱀의 시작과 끝은 Map으로 관리한다.
2. 큐가 비어있지 않고, 현재 큐의 위치가 100번 칸이 아닌 경우에 BFS 탐색한다.
3. 주사위를 1-6번 까지 굴린다.
4. 주사위를 굴린 후의 위치가 뱀과 사다리가 있는 칸이라면, 주사위를 굴린 후 위치가 아닌 뱀과 사다리를 탄 칸이 주사위를 한번 굴린 후의 위치이다.
5. 주사위를 굴린 후의 위치가 뱀과 사다리가 없는 칸이라면, 주사위를 굴린 후위치가 그대로 다음 칸 위치이다.
6. 방문한 칸 거리보다 현재 위치의 거리에서 한번 주사위를 던진 개수 보다 작다면 거리를 갱신한다.
7. 100번째 칸의 거리를 출력한다.

 

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_16928_뱀과_사다리_게임 {
    private static final int INF = (int) 1e9;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   // 사다리 개수
        int M = Integer.parseInt(st.nextToken());   // 뱀 개수

        // 사다리와 뱀 Map으로 관리
        Map<Integer, Integer> snakeAndLadder = new HashMap<>();
        for (int loop = 0; loop < N + M; loop++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            snakeAndLadder.put(start, end);
        }

        int rst = playGame(N, M, snakeAndLadder);
        System.out.println(rst);
        br.close();
    }

    private static int playGame(int n, int m, Map<Integer, Integer> snakeAndLadder) {
        boolean[] visited = new boolean[101];
        int[] distance = new int[101];
        PriorityQueue<Node> queue = new PriorityQueue<>();

        Arrays.fill(distance, INF);
        queue.add(new Node(1, 0));

        // 현재 칸이 100번째 칸이 아니면서 큐가 남아있다면
        while (!queue.isEmpty() && queue.peek().getNode() != 100) {
            Node position = queue.poll();

            if (visited[position.getNode()]) continue;
            visited[position.getNode()] = true;

            // 주사위 굴리기
            for (int dice = 1; dice <= 6; dice++) {
                int nextPosition = position.getNode() + dice;
                // 뱀과 사다리에 해당하는 칸인지 확인
                if (snakeAndLadder.containsKey(nextPosition)) {
                    if (!visited[snakeAndLadder.get(nextPosition)] && distance[snakeAndLadder.get(nextPosition)] > position.getDistance() + 1) {
                        // 뱀과 사다리를 탄 후 칸 거리를 갱신
                        distance[snakeAndLadder.get(nextPosition)] = position.getDistance() + 1;
                        queue.add(new Node(snakeAndLadder.get(nextPosition), position.getDistance() + 1));
                    }
                }
                // 뱀과 사다리에 해당하는 칸이 아님
                // 다음 칸이 100번재 칸 이하이면서 방문하지 않고, 현재 거리 + 1 보다 해당 칸 개수가 작은 경우
                else if (nextPosition <= 100 && !visited[nextPosition] && distance[nextPosition] > position.getDistance() + 1) {
                    distance[nextPosition] = position.getDistance() + 1;
                    queue.add(new Node(nextPosition, position.getDistance() + 1));
                }
            }
        }

        return distance[100];
    }

    static class Node implements Comparable<Node> {
        private int node;
        private int distance;

        public Node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        public int getNode() {
            return node;
        }

        public int getDistance() {
            return distance;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.distance, o.distance);
        }
    }
}