[백준] 16982 뱀과 사다리 게임 - Java

 

 

 

문제 출저 

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

16928번: 뱀과 사다리 게임

 

 

 

문제 풀이

주사위를 굴려 1부터 시작해서 100번째 칸에 가려합니다. 이 때, 주사위는 원하는 숫자를 뽑을 수 있고 칸에는 사다리와 뱀이 있습니다. 사다리는 낮은 숫자에서 높은 숫자로 이동하고 반대로 뱀은 높은 숫자에서 낮은 숫자로 이동합니다. 사다리와 뱀의 정보가 주어질 때, 100번째 칸으로 가기 위한 주사위를 굴리는 최소 횟수를 구해야 합니다. 

 

 

백트래킹, 메모리제이션으로 풀었습니다.

int[] board 를 통해 사다리와 뱀의 정보를 저장했습니다. 사다리 8, 52가 주어지면 board[8] = 52로 저장하였습니다.

int[] dp를 선언하여 해당 칸의 최솟값을 저장하게 하였습니다. 

 

dfs(int start) 메소드를 만들었습니다.

dfs는 int start 부터 시작해서 갈 수 있는 범위를 탐색합니다. 주사위는 정육면체로 1~6까지 이동할 수 있습니다. start에서 각각 1부터 6까지 더한 수를 구해 int next를 만들고 dp[next] 와 dp[start] + 1을 비교하여 더 작은 수를 dp[next]에 저장했습니다. 이 때, int next가 사디리와 뱀이 있다면 board[next]를 통해 가져온 값을 next에 넣었습니다. 

 

이러한 탐색을 통해 int[] dp 배열에 최솟값을 구할 수 있었고 dp[100] 을 출력하여 정답을 구했습니다. 

 

 

소스 코드 

package baekjoon.backjoon12.day0110.day07;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
뱀과 사다리 게임
https://www.acmicpc.net/problem/16928
 */
public class B16928 {
  
  static int n; // 사다리의 수 
  static int m; // 뱀의 수
  static int[] board;
  static int[] dp;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    board = new int[101];
    for(int i = 0; i < n + m; i++) {
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());
      board[start] = end;
    }

    dp = new int[101];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    dp[1] = 0;
    dfs(1);


    System.out.println(dp[100]);

  }

  public static void dfs(int start) {
    for(int i = 1; i <= 6; i++) {
      int next = start + i;

      if(next > 100) {
        return;
      }

      // 사다리든 뱀이든
      if(board[next] != 0) {
        dp[next] = dp[start] + 1;
        next = board[next];
      }

      if(dp[next] > dp[start] + 1) {
        dp[next] = dp[start] + 1;
        dfs(next);
      }
    }

  }

}