[백준 16928번 / Java] 뱀과 사다리 게임 - BFS

난이도

Gold 5

 

 

문제 링크

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

14500번: 테트로미노

 

 

---

 

 

풀이

BFS로 풀이했다.

각 너비는 주사위를 1~6번 까지 나오는 경우를 각 너비로 잡았다.

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

public class BaekJoon16928 {

    private static int N;
    private static int M;
    private static int[] ladder = new int[101];
    private static int[] snake = new int[101];
    private static boolean[] bl = new boolean[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());

        for(int i = 0; i < N + M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());

            if(i < N) ladder[before] = after;
            else snake[before] = after;
        }

        Queue<Integer> que = new LinkedList<>();
        que.add(1);

        int cnt = 0;
        while(!que.isEmpty()) {
            int size = que.size();
            cnt++;

            for(int i = 0; i < size; i++) {
                int now = que.poll();
                for(int j = 1; j <= 6; j++) {
                    int current = now + j;
                    if(current > 100) continue;
                    if(ladder[current] > 0) {
                        current = ladder[current];
                    }
                    else if(snake[current] > 0) {
                        current = snake[current];
                    }
                    if(bl[current]) continue;

                    if(current == 100) {
                        System.out.println(cnt);
                        return;
                    }
                    bl[current] = true;
                    que.add(current);
                }
            }
        }
    }
}

 

 

---

 

 

번외

N과 M이 15가 넘지 않는다고하여, 처음에는 사다리와 뱀의 경우에서 뱀은 어쨋든 아래로 내려가기 때문에

사다리만 탔을 경우를 체크하여 가장 빠른 경로를 구해보고자 했다.

 

테스트 케이스만 통과하고 오답을 뱉어냈는데, 테스트 케이스 외의 경우에서 사다리를 여러번 타야할 경우의 최적의 경로를  고려하지 못하는 코드가 되었다. 결국 사다리나 뱀을 체크해주는 배열에서 체크해주는 것이 가장 최적의 방법인 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BaekJoon16928 {

    private static int N;
    private static int M;
    private static int[] trap;
    private static int min = 100;
    private static int cnt = 100;

    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());
        List<int[]> list = new ArrayList<>();

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());

            list.add(new int[]{before, after});
        }

        trap = new int[101];

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

        int size = list.size();
        for(int i = 0; i < size; i++) {
            cnt = 0;
            findBefore(list.get(i)[0], 0);
            findAfter(list.get(i)[1], list.get(i)[1]);
        }

        System.out.println(min);

    }

    private static void findBefore(int before, int sum) {
        if(sum + 6 >= before) {
            cnt++;
            return;
        }

        for(int i = 6; i > 0; i--) {
            if(trap[sum + i] != 1) {
                sum += i;
                cnt++;
                break;
            }
        }
        findBefore(before, sum);
    }

    private static void findAfter(int after, int sum) {
        if(sum + 6 >= 100) {
            cnt++;
            min = Math.min(cnt, min);
            return;
        }

        for(int i = 6; i > 0; i--) {
            if(trap[sum + i] != 1) {
                sum += i;
                cnt++;
                break;
            }
        }
        findAfter(after, sum);
    }

}