[백준] 16928 : 뱀과 사다리 게임

문제 출처 : https://www.acmicpc.net/problem/16928

소요 시간 : 1h 30m (시도)

---

문제

---

시도

 

그냥 평소 풀던 대로 BFS를 적용했다.

 

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

public class Main {

    private static int[] board = new int[101];
    private static int[] cross = new int[101];
    private static Queue<Integer> queue = new LinkedList<>();

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

        int ladder = Integer.parseInt(line[0]);
        int snakes = Integer.parseInt(line[1]);

        int from, to;
        for(int i = 0; i < ladder + snakes; i++) {
            line = br.readLine().split(" ");
            from = Integer.parseInt(line[0]);
            to = Integer.parseInt(line[1]);

            cross[from] = to;
        }

        bfs();

        System.out.print(board[100]);
    }

    private static void bfs() {
        queue.add(1);

        while(!queue.isEmpty()) {
            int idx = queue.poll();

            int move;
            for (int i = 1; i <= 6; i++) {
                move = idx + i;

                // 이동할 곳이 한번도 방문되지 않았다면
                if(board[move] == 0) {
                    board[move] = board[idx] + 1;

                    // 이동할 곳이 도착점이라면
                    if(move == 100) return;
                    // 이동할 곳에 사다리 혹은 뱀이 있다면
                    else if(cross[move] != 0) {
                        board[cross[move]] = board[move];
                        queue.add(cross[move]);
                    }
                    // 이동할 곳에 아무것도 없다면
                    else {
                        queue.add(move);
                    }
                }
            }
        }
    }
}

 

 

IntelliJ에서 코드를 돌려보니 예시에 대해 모두 정답을 받아서 바로 제출을 했는데 8%까지 진행되더니 실패했다고 떴다.

 

---

풀이

 

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

public class Main {

    private static int[] board = new int[101];

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

        int ladder = Integer.parseInt(line[0]);
        int snakes = Integer.parseInt(line[1]);

        for(int i = 1; i <= 100; i++) board[i] = i;

        int from, to;
        for(int i = 0; i < ladder + snakes; i++) {
            line = br.readLine().split(" ");
            from = Integer.parseInt(line[0]);
            to = Integer.parseInt(line[1]);

            board[from] = to;
        }

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

    private static int bfs() {
        int[] visited = new int[101];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();

            int newNode;
            for (int i = 1; i <= 6; i++) {
                newNode = currentNode + i;

                if (newNode > 100) continue;
                // 이동할 곳이 한번도 방문되지 않았다면
                if (visited[board[newNode]] == 0) {
                    queue.offer(board[newNode]);
                    visited[board[newNode]] = visited[currentNode] + 1;
                }
                // 이동할 곳이 도착점이라면
                if (newNode == 100) return visited[100];
            }
        }

        return 0;
    }

}

 

문제였던 점은 사다리로 이동한 부분을 visited 처리하면 이후 주사위 혹은 뱀으로 이동한 경우를 고려하지 못하게 되기 때문에 `cross 이동의 경우 visited 처리를 하지 않는 것`이었다.

 

참고 출처

 - https://jumping-to-the-water.tistory.com/117

 - https://velog.io/@jaehe0413/%EB%B0%B1%EC%A4%80-16928-%EB%B1%80%EA%B3%BC-%EC%82%AC%EB%8B%A4%EB%A6%AC-%EA%B2%8C%EC%9E%84-java