뱀과 사다리 게임

맨 처음에는 문제를 읽자마자 BFS로 풀면 되네~ 했습니다. 그런데, BFS코드를 짜다가 문득 이런 생각을 하게 됐습니다.

• 뱀은 내려가니까 무조건 타면 안되잖아?
• 사다리를 탔을 때, 더 높이 올라갈 수 있으면 무조건 타면 되잖아?

이런 생각을 하고 나니

• 주사위 1 ~ 6 돌렸을 때, 가장 높게 갈 수 있는 칸만 선택해서 올라가면 되겠네?

라고 그리디를 생각하게 됐습니다. 너무 쉽다고 생각하며 코드를 다 짜고, 예제 입력을 돌려보니 정답도 나와서 제출하려고 했던 순간, 갑자기 다시 깨닫게 된 점이 있습니다.

• 그렇다면, 만약 가장 높게 올라가는 사다리를 타고 올라갔는데
• 그 사다리가 있는 칸에서 1 ~ 6 사이에 모두 뱀이 있고
• 가장 낮게 내려가는 뱀을 타고 내려갔는데
• 그 뱀으로 내려간 칸에서 6칸 내로 100으로 올라가는 사다리가 있다면?

아... 그리디가 아니었구나. 그냥 BFS로 풀어야 되는구나 라고 처음의 생각으로 돌아와서 BFS로 풀게 됐습니다.

정답

package bj.solvedac.class3;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class BJ16928 {
    private static final BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in), 1<<10
    );

    private static final int[] board = new int[101];
    private static final boolean[] visited = new boolean[101];

    public static void main(String[] args) throws Throwable {
        init();

        br.close();

        System.out.println(bfs());
    }

    private static void init() throws Throwable {
        for (int n = 1; n <= 100; n++) {
            board[n] = n;
        }

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        final int ladderSnakes = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());

        for (int i = 0; i < ladderSnakes; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            final int from = Integer.parseInt(st.nextToken());
            final int to = Integer.parseInt(st.nextToken());

            board[from] = to;
        }
    }

    private static int bfs() {
        Deque<int[]> q = new LinkedList<>();

        q.offer(new int[]{1, 0});
        visited[0] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int dice = 1; dice <= 6; dice++) {
                int to = cur[0] + dice;

                if (to == 100) {
                    return cur[1] + 1;
                }

                to = board[to];

                if (visited[to]) {
                    continue;
                }

                visited[to] = true;

                q.offer(new int[]{to, cur[1] + 1});
            }
        }

        throw new RuntimeException("UNREACHABLE CODE");
    }
}