[백준] 16928번: 뱀과 사다리 게임 (Java)

문제

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

난이도 : 골드5

알고리즘 : 그래프 탐색

 

---

풀이

• 10 x 10 크기의 보드판이지만 칸의 번호에 따라서만 이동하기에 1차원 배열을 만든다.
• 도착한 칸이 사다리면, 위로 올라가고 뱀이 있는 칸에 도착하면, 내려가지만 굳이 이를 구분하지 않고 도착 시 이동하는 칸의 번호를 1차원 배열에 저장한다.
• 1번 칸에서 시작하여 1~6을 더해가며 100번 칸에 도착할 때까지 탐색을 해야한다.
• 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해야 하므로 BFS가 적합하다고 생각했다.
• 시간 복잡도 : O(V + E)
  • V :  BFS에서 전체 노드의 개수 = 100개(칸)
  • E : 각 노드에서 탐색하는 인접 노드 = 100 x 6 (주사위 1~6)
• index와 depth를 저장하는 Node 클래스를 선언하고 Queue<Node>를 통해 BFS를 수행한다.
• 탐색 과정에서 뱀이나 사다리가 있는 칸에 도착한 경우, 즉 배열의 값이 0이 아닌 경우, 해당 값으로 이동한다.
• 탐색한 Node의 index가 100일 경우 depth를 리턴하고 BFS를 종료한다.

 

• 주사위를 던져 나온 값(1~6)을 더해가며 탐색할 때, index 값이 1차원 배열의 길이인 100을 초과하여 IndexOutOfBoundsException이 발생할 수 있으므로 이 경우 건너뛰는 로직이 필요하다.

 

 

---

코드

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

public class Main{
    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());

        int[] board = new int[101];
        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());

            board[x] = y;
        }

        int answer = bfs(board);
        System.out.print(answer);
    }

    static int bfs(int[] board){
        boolean[] isVisited = new boolean[101];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0));

        while(!q.isEmpty()){
            Node now = q.poll();
            if(now.index == 100) return now.depth;
            for(int i=1;i<=6;i++){
                int next = now.index + i;
                if(next > 100) continue;

                while(board[next] != 0){
                    next = board[next];
                }

                if(!isVisited[next]){
                    isVisited[next] = true;
                    q.add(new Node(next, now.depth+1));
                }
            }
        }

        return 0;
    }
    
    static class Node{
        int index;
        int depth;

        Node(int index, int depth){
            this.index = index;
            this.depth = depth;
        }
    }
}