백준 16928번 - 뱀과 사다리 게임

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int[] map = new int[101];
        boolean[] visited = new boolean[101];

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //사다리
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            map[first] = second;
        }

        //뱀
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            map[first] = second;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(1,0));
        visited[1] =true;

        int answer =0;

        /* bfs탐색 */
        while (!queue.isEmpty()) {
            Node current = queue.poll();

            /* 종료조건 */
            if (current.getPlace()==100) {
                answer = current.depth;
                break;
            }

            for (int i = 1; i <=6; i++) {
                int next = current.getPlace() + i;

                if (next > 100 || visited[next]) {
                    continue;
                }

                if (map[next]!=0) {
                    next = map[next];
                }

                visited[next] = true;
                queue.offer(new Node(next,current.getDepth()+1));
            }
        }

        System.out.println(answer);
    }

    static class Node {
        private int place;
        private int depth;

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

        public int getPlace() {
            return place;
        }

        public void setPlace(int place) {
            this.place = place;
        }

        public int getDepth() {
            return depth;
        }

        public void setDepth(int depth) {
            this.depth = depth;
        }
    }
}

풀이

😎bfs 풀이 방법을 알고 있다면 비교적 쉽게 풀 수 있는 문제이다.

1. 101칸의 배열을 선언해준다. (입력받은 값의 범위가 1-100이므로 101칸으로 지정)
2. 사다리와 뱀에 관한 값을 입력 받는다. 입력받은 값을 위에서 선언한 배열의 위치에 넣어준다.
3. bfs탐색을 위한 queue를 생성 시작위치인 1과 depth를 0으로 지정하여 queue에 넣는다. 이 때 visited배열의 1위치를 true로 지정해준다.
4. while문 시작 현재 위치가 100이라면 종료 아니라면 아래 for문을 돌린다.
   for문은 주사위의 칸 만큼 실행한다. 이 때 주사위를 던진 값을 현재 위치에 더하는데 100칸을 넘어가거나 이미 방문한 위치라면 continue; 만약 해당 위치에 값이 존재한다면 사다리를 타고 이동하는 것이므로 해당 값으로 현재 값을 지정 이후 visited를 true로 설정 queue에 값을 집어 넣고 다시 while문 시작
5. while문 종료 이후 answer값을 반환

🫠위에서 visited를 빼고 실행을 한다면 메모리값 부족하여 테스트를 통과하지 못한다. visited배열에 대해서 더 설명하자면 만약 next값이 이미 방문한 값이라는 소리는 현재 계산된 next값보다 더 빠르게 방문 할 수 있는 방법이 존재한다는 의미이므로 queue에 집어 넣지 않아도 된다는 의미이다.

출처 : 백준 - 뱀과 사다리 게임