BOJ_16928 : 뱀과 사다리 게임

👉 문제링크

16928번: 뱀과 사다리 게임

---

---

🔸 문제 분석 🔸

• 10 x 10 게임판에서 100개의 칸 중 첫 칸에서 마지막 칸 까지 가야한다.
  • 주사위 값을 원하는 대로 던질 수 있다.
  • 사다리를 만나면 연결 된 칸으로 내려가고, 뱀을 만나면 연결 된 칸으로 올라간다.
  • 사다리와 뱀이 겹치거나 연속 된 곳은 없다.
• 주사위 경우의 수를 BFS로 모두 확인하며 도착하는 최단 경로를 구한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static class Game {
        int num, cnt;

        public Game(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }

    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());
        int[] map = new int[101];
        boolean[] visited = new boolean[101];

        for (int i = 0; i <= 100; i++) {
            map[i] = i;
        }

        for (int i = 0; i < N + M; i++) {
            st = new StringTokenizer(br.readLine());
            map[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

        Queue<Game> que = new ArrayDeque<>();
        int now = 1;
        int cnt = 0;

        que.offer(new Game(now, cnt));

        while (!que.isEmpty()) {
            Game game = que.poll();
            now = game.num;
            cnt = game.cnt;

            if (now == 100) {
                break;
            }

            visited[now] = true;

            for (int i = 1; i <= 6; i++) {
                if (now + i <= 100 && !visited[now + i]) {
                    que.offer(new Game(map[now + i], cnt + 1));
                }
            }
        }
        System.out.println(cnt);
    }
}

🔸 코드 해석 🔸

• 뱀과 사다리를 구분 할 필요 없이, 칸을 밟으면 해당 값의 인덱스로 이동하면 된다.
• BFS에서 100칸에 도착 할 때까지 반복한다.
• 이동 횟수를 Game 객체에 저장한다..

---

🔸 end 🔸

• 이동 횟수를 저장 할 필요 없이, 큐 사이즈 만큼 반복하는 식으로 BFS를 구현했으면 Game 클래스도 만들 필요 없이 더 깔끔한 코드가 됐을 것 같다.