[Baekjoon] 16928 - 뱀과 사다리 게임

📝 문제

 

 

 

🔑 풀이 과정

· 아 정말 이 문제... 그렇게 어려워 보이지 않았는데 어제 하루종일 이것만 풀었다. 예제를 맞추니 반례가 안맞고, 반례를 맞추니 예제가 안맞고 ㅎ... 아직 골드는 많이 어렵따 ㅠ_ㅠ. 주사위 굴리는 횟수의 최소를 구하는 거니까 BFS인건 알았는데, 푸는게 어려웠다.

 

· 이 문제의 핵심은 이거다. "도착한 칸에 사다리나 뱀이 있으면, 무조건 이동해야 한다." 이동하는 것이 선택이 아니라 필수다. 예를 들어, 첫 시작인 1에서 주사위를 굴려서 갈 수 있는 칸은 2, 3, 4, 5, 6, 7 이다. 그러나 2 → 80 사다리가 있다면? 한 번 굴렸을 때 최종 도착은 80, 3, 4, 5, 6, 7 이다. 2를 방문하는 것이 아님!

 

· 문제 풀이를 위해 moves 배열을 사용했다. moves 배열은 각 칸이 최종으로 어디로 이동할지는 나타낸다. 만약 사다리나 뱀이 없으면 최종은 그 칸이다. 있으면 그 도착하는 칸의 정보를 넣어준다.

 

· 또한 BFS 할 때 큐에서 값을 꺼낼때, 현재 가지고 있는 값을 한번에 꺼내준다. 그리고 roll(굴리는 횟수)를 하나 증가시킨다. 저번에 토마토 문제 풀때 시작점이 여러개면 큐에 한 번에 넣어주고 시작하면 된다는 것을 알았는데, 이 문제를 통해서 꺼내는 것도 한번에 할 수 있다는 것을 알았다.

 

· 처음에는 평소 풀던거 처럼 100짜리 배열을 생성하고, 각 칸에 최소 이동횟수를 넣어주는 식으로 문제를 풀이했다. 그리고 사다리와 뱀의 정보를 map에 넣어주고 풀이했었다. 그랬더니 방문을 했냐 안했냐 따지는 것도 어려웠고, map에 키가 있으면 사다리와 뱀이 존재하는거니까 map.get으로 value를 꺼내고, 그걸 또 카운트를 증가시키고 !@#$%^&*( ... 매우 복잡했다.

 

 

 

🔓 답안

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

public class Main {

    static int[] moves;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //사다리의 수
        int M = Integer.parseInt(st.nextToken()); //뱀의 수

        //방문 배열 생성
        visited = new boolean[101];

        //이동해야 할 정보를 담을 moves 배열 생성
        moves = new int[101];

        //각 칸에는 이동해야 할 정보를 담는다.
        //사다리, 뱀이 있는 칸에는 결과적으로 이동하는 칸의 번호를 담고, 없는 칸은 이동이 없으므로 그냥 그 칸의 번호를 넣어준다.
        for(int i = 1; i <= 100; i++){
            moves[i] = i;
        }

        //사다리, 뱀의 정보 입력받기
        for(int i = 0; i < N+M; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            moves[x] = y;
        }

        int minMoves = snakeLadderGame();

        bw.write(minMoves + "\n");
        bw.flush();
        bw.close();
    }

    static int snakeLadderGame(){
        Queue<Integer> queue = new LinkedList<>();
        visited[1] = true;
        queue.add(1);
        int rolls = 0;

        while(!queue.isEmpty()){
            int size = queue.size();

            //큐에 존재하는 모든 원소들에 적용
            for(int i = 0; i < size; i++){
                int now = queue.remove();

                if(now == 100)
                    return rolls;

                //주사위로 이동가능한 칸이 1~6칸
                for(int j = 1; j <= 6; j++){
                    int next = now + j;

                    if((next <= 100) && (!visited[next])){
                        visited[moves[next]] = true;
                        queue.add(moves[next]);
                    }
                }
            }

            rolls++;
        }

        return -1;

    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색