[JAVA] BOJ 백준 16928번 - 뱀과 사다리 게임

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

전형적인 BFS 알고리즘 문제이다. 현재 칸이 뱀 혹은 사다리가 있는 칸이라면 이어진 칸으로 이동하고, 뱀 혹은 사다리가 없는 칸이라면 주사위를 굴려서 이동하면 된다. 

 

Tuple 클래스는 현재 번호인 v와, 주사위를 굴린 횟수인 cnt를 포함하고 있고, cnt가 작은 값을 높은 우선순위로 설정해 주었다. 그 후, 우선순위 큐에 Tuple 클래스를 넣어 100까지 도착하도록 했다.

public static void solution() {
    result = Integer.MAX_VALUE;

    play();
}

public static void play() {
    PriorityQueue<Tuple> queue = new PriorityQueue<>();
    queue.add(new Tuple(1, 0));

    boolean[][] visit = new boolean[LEN][LEN+1];

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();
        int v = tuple.v;
        int x = v / LEN;
        int y = v % LEN + 1;
        int cnt = tuple.cnt;

        if (v == LEN*LEN) {
            result = cnt;
            break;
        }

        if (v > LEN*LEN || visit[x][y]) continue;
        else visit[x][y] = true;

        // 사다리, 뱀 없음
        if (arr[x][y] == 0) {
            for (int i = 1; i <= 6; i++) {
                queue.add(new Tuple(v + i, cnt+1));
            }
        }
        else {
            queue.add(new Tuple(arr[x][y], cnt));
        }
    }
}

public static class Tuple implements Comparable<Tuple>{
    int v;
    int cnt;

    public Tuple(int v, int cnt) {
        this.v = v;
        this.cnt = cnt;
    }

    @Override
    public int compareTo(Tuple t) {
        return this.cnt - t.cnt;
    }
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B16928.java

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

class B16928 {
    static int LEN = 10;
    static int[][] arr;
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        result = Integer.MAX_VALUE;

        play();
    }

    public static void play() {
        PriorityQueue<Tuple> queue = new PriorityQueue<>();
        queue.add(new Tuple(1, 0));

        boolean[][] visit = new boolean[LEN][LEN+1];

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int v = tuple.v;
            int x = v / LEN;
            int y = v % LEN + 1;
            int cnt = tuple.cnt;

            if (v == LEN*LEN) {
                result = cnt;
                break;
            }

            if (v > LEN*LEN || visit[x][y]) continue;
            else visit[x][y] = true;

            // 사다리, 뱀 없음
            if (arr[x][y] == 0) {
                for (int i = 1; i <= 6; i++) {
                    queue.add(new Tuple(v + i, cnt+1));
                }
            }
            else {
                queue.add(new Tuple(arr[x][y], cnt));
            }
        }
    }

    public static class Tuple implements Comparable<Tuple>{
        int v;
        int cnt;

        public Tuple(int v, int cnt) {
            this.v = v;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Tuple t) {
            return this.cnt - t.cnt;
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        arr = new int[LEN][LEN+1];

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

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a/LEN][a%LEN+1] = b;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a/LEN][a%LEN+1] = b;
        }

        br.close();
    }
}

---

4. 결과 및 회고

어렵지 않은 BFS 알고리즘 문제였던 것 같다. 좀 더 난이도를 높여보자!