문제 설명

총 100개의 칸이 있으며, 각 칸마다 고유의 숫자가 순서대로 있다.
1부터 시작해서 100까지 도달해야하는데, 이때 주사위를 굴리는 최소 횟수를 구하는 것임.
현재 칸에서 주사위를 굴려 1~6칸까지 이동가능하다. 이때, 이동한 칸이 사다리 혹은 뱀과 연결되어있다면 따라서 이동해야한다.
1과 100은 사다리와 뱀이 없다.

접근

최근에 최소 거리 구하기(다익스트라 or 플로이드 워셜)를 공부해서 그런지 각 칸을 노드로 표현하고 1~6칸까지 이어진 노드들에 방향성 Edge 1이 있다고 생각하고, 뱀이나 사다리로 연결된 경우를 또 거리가 0인 방향성 Edge로 표현하면 될 것 같다고 생각했다. 노드도 100개밖에 안돼서 플로이드 워셜로 구해도 100만 정도로 예상되었기 때문이다.
그런데, 생각해보니 1부터 시작해서 100까지 가야하는거면 그냥 1부터 큐에 넣고 퍼져나가면서 가장 먼저 100에 도달한 경우가 최솟값인 것 같았다. 실제 이게 가능한게 맞는지 고민을 해보았다. 아래의 조건을 만족하면 된다고 생각했다.

i번째 칸으로 주사위를 굴려 나왔는데, 이미 i번째 칸에 방문한 적이 있는 경우 기존의 값이 i까지 가는 최솟값이므로, 큐에 다시 넣을 필요가 없다.

실제로 이 가설이 맞다고 생각했고, 문제를 BFS로 풀기로 했다.

첫번째 풀이의 실패

문제를 제대로 안읽었다. 생각해보니 사다리를 타고 내려갔는데 다시 사다리 or 뱀이 있는 경우가 있을 수 있었다.

두번째 풀이의 실패

첫번째 풀이의 실패한 코드를 수정하며 main함수의 덩치를 너무 키우다보니 가독성이 안좋아져서 실수를 했다.

세번째 풀이 성공

알고리즘에서도 함수 분리가 중요하다는 것을 다시금 깨닫고, 현재 지점에서 사다리와 뱀을 타고 쭉쭉 내려갔을때의 최종 위치를 반환하는 move 함수를 만들었다. 만약 그 중간 과정에서 방문한 적이 있는 노드가 있다면 이 경우는 굳이 큐에 넣을 필요가 없으므로 실패의 의미인 -1을 반환한다.

    static boolean[] isVisited = new boolean[101];
    static int[] sadari = new int[101];
    static int[] snake = new int[101];

    static class Node {
        final int number;
        final int depth;

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

    private static int move(int start) {
        if (isVisited[start]) return -1;
        isVisited[start] = true;

        int sadariNext = sadari[start];
        if (sadariNext != 0) {
            if (!isVisited[sadariNext]) return move(sadariNext);
            else return -1;
        }

        int snakeNext = snake[start];
        if (snakeNext != 0) {
            if (!isVisited[snakeNext]) return move(snakeNext);
            else return -1;
        }
        return start;
    }

그리고 위의 move함수를 활용하는 main함수의 BFS 로직은 다음과 같다.

        int result = 0;
        LinkedList<Node> q = new LinkedList<>();
        q.add(new Node(1, 0));
        while (!q.isEmpty()) {
            Node cur = q.poll();
            isVisited[cur.number] = true;
            boolean isFind = false;

            for (int i = 1; i <= 6; i++) {
                int next = cur.number + i; // 주사위 굴려 나온 수.
                if (next > 100 || isVisited[next]) continue;
                if (next == 100) {
                    isFind = true;
                    result = cur.depth + 1;
                    break;
                }
                next = move(next);
                if (next != -1) {
                    q.add(new Node(next, cur.depth + 1));
                }
            }

            if (isFind) break;
        }

        System.out.println(result);

느낀점

드디어 백준 클래스3의 마지막 골드문제까지 다 풀었고 남은 실버문제 4개만 해치우면 클래스3이 끝난다. 클래스 2,3 통틀어서 가장 헤맨 문제였던 것 같다.
최근에 프로젝트로 바빠서 5일 정도 안풀었다고 감을 잃은건지, 함수 분리를 안해서 그런건지, 코틀린으로 풀다가 자바로 해서 그런건지,,, 클래스 2,3 통틀어서 가장 헤맨 문제였던 것 같다.
자바로 코테 푸는 것에 좀 더 익숙해져야겠다는 생각과 알고리즘 풀 때도 함수분리를 하자는 것을 다시 한 번 상기했다.