[백준] 뱀과 사다리 게임 JAVA

반응형

728x90

[백준] 뱀과 사다리 게임 - GOLD V 16928

---

접근

• bfs

---

풀이

단순한 주사위를 사용한 보드게임으로 사다리가 있는 칸이라면 사다리를 타고 앞의 칸으로 이동하게 되고 뱀이 있는 칸이라면 뱀에 미끄러져 밑에 칸으로 떨어지게 되는 게임에서 몇 턴만에 마지막 칸에 도달할 수 있는지 구하는 문제이다. 문제를 보고 굉장히 단순해 보여 금방 풀고 넘길 수 있을 거 같았는데 잘못된 생각으로 시간을 날려먹고 중복 처리를 실수해 메모리 초과로 한 번 더 시간을 날려먹은 문제이다.

 

첫 번째로 잘못된 생각이란 사다리의 경우 한 번에 많은 칸을 전진할 수 있기 때문에 무조건 타는게 좋다고 생각했다. 뱀의 경우 강제로 많은 칸을 후진 당하기 때문에 다음 위치가 뱀이라면 큐에 추가하지 않고 일반 칸이거나 사다리 칸만 큐에 넣으면 되는 게 아닌가 생각을 하고 코드를 짰다. 그러다 한 반례를 보고 뱀과 사다리를 적절하게 조합을 했을 때 최단 경로가 나온다는 것을 깨달았고 뱀 칸이 나오더라도 큐에 추가해주었다.

    private static class Player {
        private final int location;
        private final int turn;

        public Player(int location, int turn) {
            this.location = location;
            this.turn = turn;
        }
    }

큐에 들어갈 플레이어 클래스이다. 현재 위치와 몇 번째 턴인지 저장하는 내부 필드를 가지고 있다.

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);

        Map<Integer, Integer> snakeAndLadderMap = new HashMap<>();

        for (int i = 0; i < N + M; i++) {
            String[] input = br.readLine().split(" ");
            snakeAndLadderMap.put(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
        }
        
        int result = getResultWithBfs(snakeAndLadderMap);

뱀과 사다리의 칸을 입력받아 맵에 저장했다. 처음엔 배열에 뱀과 사다리 각각 나눠 저장했는데 생각해보니 굳이 그렇게 나눌 필요가 없을거 같아 맵에 저장했다.

    private static int getResultWithBfs(Map<Integer, Integer> snakeAndLadderMap) {
        Queue<Player> que = new LinkedList<>();
        que.offer(new Player(1, 0));
        boolean[] isVisited = new boolean[101];
        isVisited[1] = true;

큐에 초기값을 설정하고 보드의 경우 1부터 100까지 칸을 사용하기 때문에 크기를 방문배열을 크기를 101로 설정했다.

	while (!que.isEmpty()) {
            Player player = que.poll();

            if (player.location == 100)
                return player.turn;

            for (int d = 1; d <= 6; d++) {
                int next = player.location + d;

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

bfs를 수행하는 부분이다. 위치가 100이 되면 결과 턴을 리턴하게 되고 주사위의 1부터 6까지의 경우로 다음 위치를 추가하게 된다. 결과가 100번째 칸을 넘어간다면 이동할 수 없고 방문체크를 통해 중복을 걸러준다.

		boolean isQueAdded = false;

                for (Integer key : snakeAndLadderMap.keySet()) {
                    if (next == key) {
                        next = snakeAndLadderMap.get(key);
                        que.offer(new Player(next, player.turn + 1));
                        isVisited[next] = true;
                        isQueAdded = true;
                    }
                }

                if (!isQueAdded) {
                    que.offer(new Player(next, player.turn + 1));
                    isVisited[next] = true;
                }

맵을 순회하며 해당 칸이 사다리 또는 뱀 칸인지 확인하고 그렇다면 해당 칸을 통해 이동된 위치가 다음 위치로 변경되고 방문 체크를 진행해준다. 만약 해당 칸이 사다리와 뱀 칸이 아니라면 이동된 위치를 다음칸으로 큐에 추가하고 방문체크를 진행해준다.

---

전체 코드

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {
    private static class Player {
        private final int location;
        private final int turn;

        public Player(int location, int turn) {
            this.location = location;
            this.turn = turn;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NM = br.readLine().split(" ");
        int N = Integer.parseInt(NM[0]);
        int M = Integer.parseInt(NM[1]);

        Map<Integer, Integer> snakeAndLadderMap = new HashMap<>();

        for (int i = 0; i < N + M; i++) {
            String[] input = br.readLine().split(" ");
            snakeAndLadderMap.put(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
        }

        int result = getResultWithBfs(snakeAndLadderMap);

        System.out.println(result);
        br.close();
    }

    private static int getResultWithBfs(Map<Integer, Integer> snakeAndLadderMap) {
        Queue<Player> que = new LinkedList<>();
        que.offer(new Player(1, 0));
        boolean[] isVisited = new boolean[101];
        isVisited[1] = true;

        while (!que.isEmpty()) {
            Player player = que.poll();

            if (player.location == 100)
                return player.turn;

            for (int d = 1; d <= 6; d++) {
                int next = player.location + d;

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

                boolean isQueAdded = false;

                for (Integer key : snakeAndLadderMap.keySet()) {
                    if (next == key) {
                        next = snakeAndLadderMap.get(key);
                        que.offer(new Player(next, player.turn + 1));
                        isVisited[next] = true;
                        isQueAdded = true;
                    }
                }

                if (!isQueAdded) {
                    que.offer(new Player(next, player.turn + 1));
                    isVisited[next] = true;
                }
            }
        }
        return -1;
    }
}