[백준] no16928: 뱀과 사다리 게임

문제

사다리 : 100에 더 가까운 자리로 올라감

뱀 : 1에 더 가까운 자리로 내려감

다이스 : 1~6까지의 경우가 있음

1~100까지의 칸으로 구성된 Map에서 100으로 가는 최소 다이스 횟수 구하기

 

문제 링크 : https://www.acmicpc.net/problem/16928

---

원리

1. 그래프 탐색

2. 너비우선탐색 (BFS)

 

---

풀이방법

1. 재귀형 다이스

/**
 * 0. dice는 1로 초기화 (첫 다이스용), minDice는 maxValue 혹은 100
 * 1. static메소드로 주사위 이동 만들기 : for(int i =1 ; i <=6 ; ++) 로 주사위 굴리고, position = 100이 되면 dice(주사위 굴린 횟수)가 minDice보다 작으면 교체 안그럼 무시하고 재귀 중지
 * 2. 위의 메소드를 1~6까지 반복 (첫 다이스)
 * 3. Integer 타입의 map 안에 각 칸에 도착하면 이동하게될 경로 표시. null이면 그 자리에 스톱.
 * 4. now는 이동이 완료된 현위치
 * 5. map의 1번자리부터 시작. 이동 가능한 모든 경로를 이동해봄
 * 6. 각 이동을 통한 100에 도달하면, 현재까지의 Dice수를 minDice와 비교. 더 작으면 최소다이스 횟수는 현재 다이스 횟수
 */

2. 너비우선탐색 (BFS)

: 원리는 비슷하다.

: queue에 가야할 위치를 순차적으로 넣고 계산할 값만 하나씩 빼서 계산한다.

: 만약 목적지에 도착하면 다른 계산은 queue에서 전부 제거해서 불필요한 계산은 하지 않는다는게 포인트

---

나의 코드

1. 재귀형 다이스 [ StackOverflow 발생 ]

import java.io.*;
import java.util.StringTokenizer;

public class no16928 {
    static int N;
    static int M;
    static int minDice;

    static Integer[] map = new Integer[101];

    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());
        minDice = 100000000;

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

        for(int i = 1; i<=6 ; i++) MOVE(i, 1);

        System.out.println(minDice);
    }

    private static void MOVE(int position, int dice) {
        if(position>=100) {
            if(dice<=minDice) minDice = dice;
            return;
        }
        for(int i=1; i<=6; i++) {
            position += i;
            if(position>=100) position = 100;
            else if(map[position]!=null) position = map[position];

            MOVE(position, dice+1);
        }
    }
}

 

2. 너비우선탐색 (BFS)

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class no16928 {
    static Integer[] map;

    static int minDice;

    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());
        map = new Integer[101];  // 100번 인덱스까지 해야하므로 101칸
        minDice = 100000;

        // 입력받아 map을 만들어줌 (1열로 나열)
        for(int i=0; i<N+M; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            map[Integer.parseInt(st2.nextToken())] = Integer.valueOf(st2.nextToken());
        }

        BFS();

        System.out.println(minDice);
    }




    private static void BFS() {
        // 현위치 저장 및 반환하는 dq
        Deque<Integer> dq = new ArrayDeque<>();
        boolean[] visited = new boolean[101];

        visited[1] = dq.offer(1); // offer : add 성공시 true | 실패시 false 반환
        int dice = 0; // 주사위 롤 횟수

        while(!dq.isEmpty()) {
            dice++;
            int size = dq.size();

            for (int i = 0; i < size; i++) {
                int now = dq.poll(); // 출발위치

                // 주사위의 1~6경우의 수
                for(int plus = 1 ; plus <=6 ; plus++) {
                    int next = now + plus;

                    // 방문한 곳이거나, 0보다 작거나, 이미 종점이면 제껴라
                    if(next < 0 || next > 100 || visited[next]) continue;

                    // 100에 도착했을 경우
                    if(next == 100) {
                        if(dice<=minDice) {
                            dq.clear();
                            minDice = dice;
                            return;
                        } else continue;
                    }

                    // 일반 칸일때
                    if(map[next] == null) {
                        dq.add(next);
                        visited[next] = true;
                    }

                    // 사다리나 뱀이 있는 칸일 경우.
                    else {
                        if(visited[map[next]]) continue; // 방문 한 칸일 경우
                        dq.add(map[next]);
                        visited[map[next]] = true;
                    }
                }
            }
        }

    }
}

 

 

---

레퍼런스 코드

참고 링크 : https://kwangkyun-world.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-16928-%EB%B1%80%EA%B3%BC-%EC%82%AC%EB%8B%A4%EB%A6%AC-%EA%B2%8C%EC%9E%84