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

문제

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

[16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net](https://www.acmicpc.net/problem/16928)

풀이

bfs를 통하여 문제를 풀었습니다. 처음에 방문체크를 하지 않고 했더니 메모리 초과가 뜨네요. 한 번 방문한 지점은 다시 방문했을 때 큐에 들어가지 않도록 해주는 과정이 중요합니다.

• map에 사다리와 뱀 값을 넣어줍니다.
• 큐에 현재 위치와 움직인 횟수 정보를 담은 Info클래스를 생성해줍니다.
• bfs를 통해 큐에 시작 위치 1과 카운트 값 0을 넣고 시작합니다.
• 1부터 6까지 주사위를 for문을 통해 돌려줍니다.
• 더해진 현재위치가 100일 경우 현재 카운트값을 반환해줍니다.
• 100 보다 더 큰 숫자일 경우에는 아무것도 하지 않습니다.
• 이미 방문한 위치라면 아무것도 하지 않습니다.
• map에서 현재위치에 사다리나 뱀이 있는지 확인한 후 있다면 이동시킵니다.

코드

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

public class Main {

    static int n;
    static int m;
    static Map<Integer, Integer> map = new HashMap<>();
    static boolean[] visited = new boolean[101];

    static class Info {
        int cnt;
        int idx;

        public Info(int cnt, int idx) {
            this.cnt = cnt;
            this.idx = idx;
        }
    }

    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());
            map.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        System.out.println(bfs());
    }

    public static int bfs() {
        Queue<Info> queue = new LinkedList<>();
        queue.offer(new Info(0, 1));

        while(!queue.isEmpty()) {
            Info info = queue.poll();

            // 주사위 1~6까지 던지기
            for (int i = 1; i <= 6; i++) {
                int cur = info.idx + i;
                // 100이면 도착이므로 카운트 값을 리턴합니다.
                if (cur == 100) {
                    return info.cnt + 1;
                }
                // 100 보다 크다면 아무것도 하지 않습니다.
                if (cur > 100) {
                    continue;
                }
                // 이미 방문한 숫자라면 경우의 수를 줄이기 위해 중복되지 않도록 넘어갑니다.
                if (visited[cur]) {
                    continue;
                }
                Integer num = map.getOrDefault(cur, 0);
                // 사다리나 뱀이 해당 칸에 있는지 확인합니다.
                if (num == 0) {
                    queue.offer(new Info(info.cnt + 1, cur));
                    visited[cur] = true;
                } else {
                    queue.offer(new Info(info.cnt + 1, num));
                    visited[num] = true;
                }
            }
        }
        return -1;
    }
}