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

 

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

16928번: 뱀과 사다리 게임

1. 문제 설명

 

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

 

2. 풀이

 

BFS로 풀 수 있다.

 

1부터 시작하여 주사위 (1~6까지)를 굴러가며 이동한다.

움직이는 위치에 사다리/뱀이 있는 경우 그 자리로 이동한다.

이미 방문하지 않았던 경우만 BFS 탐색을 진행해나가면서 100에 처음으로 도착하는 움직이는 횟수를 출력한다.

 

3. 코드

// JAVA 11, 시간 : 144ms , 메모리 : 14260KB


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

public class Main {

    // 게임판 상황 파악
    public static int[] map = new int[101];
    // 방문 체크
    public static boolean[] visited = new boolean[101];
    // 사다리 개수, 뱀 개수
    public static int ladderNum, snakeNum;

    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 = new StringTokenizer(br.readLine());

        ladderNum = Integer.parseInt(st.nextToken());
        snakeNum = Integer.parseInt(st.nextToken());

        for (int x = 0; x < ladderNum+snakeNum; x++) {
            st = new StringTokenizer(br.readLine());

            map[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());

        }

        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        visited[1]=true;

        int answer = 0;
        boolean find=false;

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


            for (int x = 0; x < size; x++) {
                int now = queue.poll();

                // 100 도착
                if (now == 100) {
                    find=true;
                    break;
                }

                for (int y = 1; y <= 6; y++) {
                    // 100번 칸을 넘어가면 이동할 수 없음 -> 100번 칸 이하로 이동 가능
                    if(now+y<=100){

                        int next = now + y;

                        // 사다리나 뱀이 있는 경우 타고 이동
                       if (map[next] > 0) {
                            next = map[next];
                        }

                       // 이전에 방문하지 않았던 경우만 이동
                        if(!visited[next]){
                            visited[next]=true;
                            queue.add(next);
                        }
                    }
                }
            }
            if(find)
                break;

            answer++;
        }

        bw.write(String.valueOf(answer));

        bw.flush();

    }
}