[백준] 16928 - 뱀과 사다리 게임 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

16928번: 뱀과 사다리 게임

문제

뱀과 사다리 게임을 즐겨하는 큐브 러버는 어느 날 궁금한 점이 생겼다.

주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

입력
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력
100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

접근방법

 1에서 출발해 100까지 가기 위해 사용되는 주사위의 최소 개수를 구하면 된다. 사다리는 지향하되, 뱀은 지양하면서 가장 큰 주사위로 100번까지 가는 것이 가장 최소의 방법일 것이다. 어떻게 하면 최소가 될까 고민하면서, 풀이로 들어가자.

 

실패 원인

 나는 위의 접근방법을 그대로 옮겨서 코딩하려고 했다. HashMap 두 개를 이용하여 사다리와 뱀을 표현했다. 문제는 사다리였다. 사다리를 제대로 활용하기 위해서 value값으로 내림차순 정렬을 하였다. 그래서 가장 value 값이 높은 key 값과 그보다 낮은 value 값을 가진 사다리 중 key값도 낮은 레코드를 확인하여 연결하고, 그것으로 문제를 구현했다. 문제의 두 예제는 통과하였으나, 시간 초과를 넘지 못했다. value로 sorting 하는 것도 시간이 걸리지만, 최악의 경우 모든 사다리를 이용할 수 있다는 가정하에 O(N^2)의 시간이 걸릴 것이다. 주사위를 돌리기도 전에 이미 사다리 배치에서 시간 초과가 난 것이다. 그래서 생각을 바꿨다. 바로 BFS를 이용하는 것이다.

 

풀이

 나는 해당 문제를 풀기 위해 BFS 방식을 이용했다. 먼저 배열부터 정의했다. 자연수로 맞추기 위해 101개의 배열을 생성한 뒤, 배열[N]에 들어갈 값은 N으로 갈 때 소모되는 가장 적은 주사위 횟수로 정의했다.

 

그다음엔 BFS로 뻗어 나갈 수 있는 경우의 수를 생각해보았다.

 시작점에서부터 출발할 때, 주사위 한 번에 따라 6가지 위치(사다리 , 뱀 포함)로 이동할 수 있다. 해당 위치가 사다리 위치 거나 뱀의 위치라면, 그로 인해 이동된 위치를 반환하고, BFS를 계속 진행했다. 또한 해당 위치가 이미 BFS의 다른 노드에 의해 이미 지나간 곳이라면, 더 짧게 지나갈 수 있는 방법의 수만을 해당 자리에 값으로 남겼다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Main test = new Main();

    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        Map<Integer,Integer> ladder = new HashMap<>();
        Map<Integer,Integer> snake = new HashMap<>();

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

            ladder.put(Integer.parseInt(stk.nextToken()),Integer.parseInt(stk.nextToken()));
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            snake.put(Integer.parseInt(stk.nextToken()),Integer.parseInt(stk.nextToken()));
        }


        System.out.println(solution(ladder, snake));

    }

    private int solution( Map<Integer,Integer> ladder,  Map<Integer,Integer> snake) {


        int[] field = new int[101];
        Arrays.fill(field,Integer.MAX_VALUE);
        //param : cur_loc , move_cnt
        Queue<IntPair> queue = new LinkedList<>();
        queue.add(new IntPair(1,0));
        field[1] = 0;

        while (!queue.isEmpty()){

            IntPair cur_info = queue.poll();
            //System.out.println("현재 위치 : \t" +cur_info.left+ "\t cnt :" +cur_info.right);
            if( cur_info.left == 100){
                break;
            }

            int move_cnt = cur_info.right+1;

            for (int i = 6 ; i >0 ;i--){
                int next_cur = cur_info.left;
                next_cur+=i;
                if(next_cur > 100){
                    continue;
                }
                //뱀을 타고 내려가야만 하는 경우도 고려해야함
                if(snake.containsKey(next_cur)){
                    next_cur = snake.get(next_cur);
                }

                //사다리를 탈 수 있다면 탄 위치로
                else if (ladder.containsKey(next_cur)){
                    //System.out.println("사다리 탐!!!!");
                    next_cur = ladder.get(next_cur);

                }

                //해당 필드에 있는 값보다 지금값이 더 작을때만 작동
                if(field[next_cur] > move_cnt){
                    field[next_cur] = move_cnt;
                    queue.add(new IntPair(next_cur,move_cnt));
                }

            }
        }



        return field[100];
    }



    class IntPair{
        Integer left;
        Integer right;

        public IntPair(Integer left, Integer right) {
            this.left = left;
            this.right = right;
        }
    }

}

 

결과

 

 이 문제 때문에 근 2달 만에 1일 1문제 포스팅이 끊겼다..ㅠㅠ 해결하기 위해서 하루를 고민했다... BFS에 대해 그래프 완전 탐색이라는 생각을 갖고 있다 보니, 이렇게 흐름 제어를 통해 풀 수 있다고 생각을 못한 것이 시간 손해의 큰 원인으로 보인다. 결국 문제를 손으로 그려보다가 BFS를 시도해보게 되었고, 정답을 도출할 수 있었다. 문제 그 자체보다 해결하는 콘셉트를 빠르게 찾아낼 수 있도록 공부해야겠다.  

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.