[백준] 16928번 : 뱀과 사다리 게임 (JAVA)

인간몽쉘김통통·2023년 5월 20일

그래프 탐색 백준 알고리즘

백준

목록 보기

9/92

문제

풀이

이해

뱀과 사다리 게임은 보드 내에 뱀과 사다리로 이루어진 통로(지름길)을 이용하여 최종 목적지까지 빠르게 도달하는 게임이다. 보통 사다리는 지름길, 뱀은 함정 같은 역할을 한다.

문제에서는 100x100의 보드에서 사다리 게임을 진행하는데 뱀과 사다리에 대한 정보를 입력받는다. 1부터 출발하여 100까지 가장 빠르게 도달할 수 있는 수를 출력받아야 한다.

접근

100으로의 최소값을 구해야하므로 적용할 수 있는 알고리즘은 브루트포스, 그리디, 너비 탐색 정도가 있겠다. 브루트포스는 선택할 수 있는 100까지의 경로까지의 모든 값을 구한 뒤 최소값을 구해야 하는데 애초에 주사위 1~6 그리고 뱀, 사다리까지 제어해야 할 변수가 너무 많기 때문에 브루트포스는 적절하지 않다.

그렇다면 그리디는 어떨까? 다이내믹 프로그래밍 방식으로 그리디 알고리즘 풀이를 생각해봤는데 이 역시 쉽지 않다. 마찬가지로 뱀, 사다리까지 포함한 너무 많은 변수 때문이다.

마지막으로 탐색을 어떨까? 목적지까지의 최소값을 구하기 위해서는 그래프의 너비 우선 탐색이 효과적으로 보인다. N에서 출발해서 갈 수 있는 노드는 어딜까? N+1 ~ 6인 주사위로 갈 수 있는 노드가 있고 예외적으로 뱀, 사다리로 갈 수 있는 경우가 있겠다.

그래프의 BFS가 가장 좋아보이는 방법인데 여기서 유의해야 하는 점은 사다리, 뱀이 있는 칸으로 이동하는 경우 무조건 이동해야 한다.

이 점에 유의해서 코드를 작성해보았다.

코드

package java_baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class prob16928 {
    static class node {
        int num;
        int depth;

        public node(int num, int depth) {
            this.num = num;
            this.depth = depth;
        }
    }

    static boolean visited[] = new boolean[101];
    static int ans = 0;
    static int[] snake_ladder_before;
    static int[] snake_ladder_after;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        snake_ladder_before = new int[N + M];
        snake_ladder_after = new int[N + M];
        int cnt = 0;

        while (N-- > 0) {
            snake_ladder_before[cnt] = sc.nextInt();
            snake_ladder_after[cnt] = sc.nextInt();
            cnt++;
        }
        while (M-- > 0) {
            snake_ladder_before[cnt] = sc.nextInt();
            snake_ladder_after[cnt] = sc.nextInt();
            cnt++;
        }

        // BFS
        Queue<node> que = new LinkedList<node>();
        que.add(new node(1, 0));
        visited[1] = true;

        while (!que.isEmpty()) {
            node cur_node = que.poll();

            if (cur_node.num == 100) {
                ans = cur_node.depth;
                break;
            }

            // 주사위 탐색, 뱀 사다리 탐색
            for (int i = cur_node.num + 1; i <= cur_node.num + 6 && i <= 100; i++) {
                int j = 0;
                for (; j < snake_ladder_before.length; j++) {
                    if (snake_ladder_before[j] == i && !visited[i]) {
                        que.add(new node(snake_ladder_after[j], cur_node.depth + 1));
                        visited[i] = true;
                        break;
                    }
                }
                if (j == snake_ladder_before.length && !visited[i]) {
                    que.add(new node(i, cur_node.depth + 1));
                    visited[i] = true;
                }
            }
        }

        System.out.println(ans);

        sc.close();
        return;
    }
}