자바(백준) 16928 뱀과 사다리 게임

오답 노트 & 새로 알게 된 점

문제를 처음에 접근할 때는 클래스를 구성해서 x, y좌표를 따로 저장한 뒤에 무조건 사다리를 건너야하며 등등 어렵게 생각을 했다. 그리고, 1~6일 때 모두 큐에 넣는다면 터질 것 같아서 도저히 풀이 방법이 생각나질 않았다. 그러나 구글링을 통하여 힌트를 얻었고, 문제를 풀 수 있었다.

 

이차원 배열을 사용하지 않고

사다리나 뱀이 있는 경우 시작점을 배열의 index, 도착점을 배열의 value로 설정한다. 그래서 해당 배열의 값이 0이 아니게 되면 도착점을 큐에 넣어준다. 

사다리나 뱀이 없는 경우 그냥 count만 1 늘려준다.

 

---

오답 노트 & 새로 알게 된 점 ( 2021.10.24)

문제를 다시 풀어보았는데 틀렸다.

처음에 생각한 점이 뱀은 무조건 지나면 안된다였다. 

주사위 최소값을 가져야하는데 뱀을 지나게 되면 무조건 최소값을 가질 수 없다고 생각했다.

그러나 혼자 반례를 생각해보았다.

 

14번에 사다리가 있다고 생각해보자.

그렇다면 주사위로만 14번에 가려면 1 + 6 + 6 + 1로 총 3번 굴려야한다.

하지만 1 -> 2 (사다리) -> 16 -> 17 (뱀) -> 14로 가면 2번만에 갈 수 있게 된다.

그래서 뱀도 지나치면서 최소값을 가질 수 있다고 생각이 들었다.

 

 

---

코드

package BFS;
 
//BOJ 16928 뱀과 사다리 게임
 
import java.util.*;
import java.io.*;
 
public class BOJ16928 {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    static boolean visit[] = new boolean[101];
    static int count[] = new int[101];
    static int block[] = new int[101];
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int r_size = atoi(st.nextToken());
        int s_size = atoi(st.nextToken());
 
        for(int i = 0; i < r_size+s_size; i++){
            st = new StringTokenizer(br.readLine());
            int start = atoi(st.nextToken());
            int end = atoi(st.nextToken());
            block[start] = end;
        }
        ////////////////////////////////////////////////입력 끝
 
        bfs();
 
    }
    static void bfs(){
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);
        visit[1] = true;
 
        while(!q.isEmpty()){
            int element = q.poll();
 
            if(element == 100){
                System.out.print(count[100]);
                return;
            }
 
            for(int i = 0; i < 6; i++){
                int X = element + ( i + 1 );
                if(!isRangeTrue(X)) continue;
                if(visit[X]) continue;
                visit[X] = true;
 
                if(block[X] != 0){
                    if(!visit[block[X]]) {
                        q.offer(block[X]);
                        visit[block[X]] = true;
                        count[block[X]] = count[element] + 1;
                    }
                }
                else {
                    q.offer(X);
                    count[X] = count[element] + 1;
                }
            }
        }
    }
    static boolean isRangeTrue(int x){
        return x < 101;
    }
}