BOJ G5 16928 뱀과 사다리 게임 JAVA

16928번: 뱀과 사다리 게임

---

문제 읽기

이 문제는 1차원 배열과 bfs, visited를 활용해서 쉽게 해결했다. 주사위 횟수의 최솟값이므로 dfs와 bfs 중에서 bfs를 선택했다.

---

문제 풀기

크게 어렵지 않다. 일차원 배열을 사용해서 각 번호를 가진 칸마다 뱀 또는 주사위가 있는 칸이면 값으로 이동할 칸의 번호를 넣어주었다. 이를 활용해서 1부터 시작해서 100에 도달할 때까지 계속 큐에 넣고 하면 답이 나온다.

코드로 보는 게 더 쉬울 것이다.

---

코드

package ps.GraphSearch;

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 BOJ_G5_16928_뱀과사다리게임 {
    static class Pos{
        int no;
        int depth;
        public Pos(int no, int depth){
            this.no = no;
            this.depth = depth;
        }
    }
    static int upN, downN;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        upN = Integer.parseInt(st.nextToken());
        downN = Integer.parseInt(st.nextToken());
        int[] map = new int[101];
        for (int i = 0; i < upN + downN; i++){
            st = new StringTokenizer(in.readLine());
            map[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

        Queue<Pos> q = new ArrayDeque<>();
        boolean[] visited = new boolean[101];
        q.offer(new Pos(1, 0));
        visited[1] = true;
        while(!q.isEmpty()){
            Pos cur = q.poll();

            for (int dice = 1; dice <= 6; dice++){
                int next = cur.no + dice;
                if (next <= 100 && map[next] != 0) next = map[next];
                if (next == 100) {
                    System.out.println(cur.depth + 1);
                    return;
                }

                if (next < 1 || next > 100 || visited[next]) continue;

                visited[next] = true;
                q.offer(new Pos(next, cur.depth+1));
            }
        }
    }
}