백준 Q16928 뱀과 사다리 게임

in Algorithm on baekjoon


문제

뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.

“주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?”

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

입력

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

풀이

일단 풀기 전 이 문제는 삼성전자 코딩테스트 기출문제임을 먼저 알린다. 그렇다고해서 쫄지는 말지어다.
문제에서 알 수 있는 것은 시작과 끝을 알 수 있다. 바로 1로 시작해서 100으로 최소로 방문하는 것이 목표이다.
그리고 이동할 수 있는 경우의 수는 현재 위치에서 주사위 값만틈 더한 경우니 총 6가지이다.
그리고 이동 후 도착한 지점에 뱀 또는 사다리가 있는 경우 그것을 타고 이동된 곳도 방문하게 된다.

위 정보들을 요약을 하면…

  • 시작은 1, 끝은 100
  • 1에서 100까지 최소 방문 횟수는?
  • 경우의 수는 X -> X+1,2,3,4,5,6
  • 이동시 도착한 곳에 뱀/사다리 자리라면 그것의 목적지도 방문된다.

이제 풀어본다면 우선 뱀/사다리 정보를 기억해준다. A에서 B로 바로가는 구조이기 때문에 Map을 사용해서 저장해준다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");

int n = Integer.parseInt(line[0]); // 사다리 수
int m = Integer.parseInt(line[1]); // 뱀 수

//사다리 수만큼 입력
for(int i = 0; i < n; i++){
    line = br.readLine().split(" ");
    int ladderStart = Integer.parseInt(line[0]);
    int ladderEnd = Integer.parseInt(line[1]);
    ladderSnakeMap.put(ladderStart, ladderEnd);
}

//뱀 수만큼 입력
for(int i = 0; i < m; i++){
    line = br.readLine().split(" ");
    int snakeStart = Integer.parseInt(line[0]);
    int snakeEnd = Integer.parseInt(line[1]);
    ladderSnakeMap.put(snakeStart, snakeEnd);
}

이후 시작점 1을 기준으로 +1, +2, +3, +4, +5, +6 순으로 너비 탐색을 진행한다. 탐색을 진행하면서 방문여부를 체크를 하여 최소 방문 횟수를 각 지점마다 저장을 해준다.
그리고 방문시 뱀/사다리에 해당하는지도 체크하면서 뱀/사다리의 도착점의 방문여부도 체크한 다음. 마찬가지로 최소 방문 횟수를 도착점에 기록을 해준다.

여기서 너비 탐색하는 방법은 Queue 자료구조를 이용하는 것이다. 이용하는 방법은 다음과 같다.

  1. 시작점을 Queue에 넣는다.
  2. Queue의 HEAD부분을 뺀 것을 기준으로 모든 경우의 수에 해당하는 것에 대해서 유효성을 확인한 후 Queue에 넣어준다.
  3. 2번 과정을 Queue가 빌 때까지 진행한다.

이 과정을 이 문제에 대입하면…

  1. 시작점 1을 Queue에 넣는다.
  2. Queue의 HEAD부분을 뺀 지점의 +1 ~ +6의 해당하는 지점의 유효성을 확인한다.
  3. 이 문제에서 유효성은 도착지점이 처음으로 도착하는지 여부와 도착지점이 100을 넘지 않는 것이다.
  4. 또한 뱀/사다리에 해당하는지 확인하여 해당시 도착지점도 위의 유효성을 확인한다.
  5. 해당 도착지점의 유효성 검사가 통과되는 그 지점에 최소 방문 횟수를 표시하고 Queue에 넣어준다.
  6. 2번 ~ 5번 과정을 Queue가 빌 때까지 반복한다.

여기서 최소방문 횟수 및 방문 여부를 확인하기 위해 기록이 필요한 배열(visitMap)을 따로 만든다. 값이 -1이면 방문 안한 것이고, 0은 시작점, 그외 자연수는 최소 방문 횟수를 의미한다.

이에 대한 로직을 구현한 결과 다음 코드와 같다.

private static void goLadderGame(Map<Integer, Integer> ladderSnakeMap){
    Queue<Integer> visitQueue = new LinkedList<>();

    int start = 1; //시작
    int end = 100; //끝
    int[] visitMap = new int[101]; // 1~100까지 최소방문횟수 기록할 공간 visitMap
    Arrays.fill(visitMap, -1); //아직 방문 안된곳은 -1로 설정

    visitMap[start] = 0;
    visitQueue.add(start);

    //Queue를 이용하여 너비 우선 탐색(BFS) 진행
    while(!visitQueue.isEmpty()){
        int currentPosition = visitQueue.poll();

        // 주사위 1~6 너비 탐색
        for(int dice = 1; dice <= 6; dice++){
            int nextPosition = currentPosition + dice;

            // 100 이상 이동 불가
            if(nextPosition > end){
                continue;
            }

            //첫 방문 시 이전 방문 횟수 + 1
            if(visitMap[nextPosition] == -1){
                visitMap[nextPosition] = visitMap[currentPosition] + 1;

                // 뱀사다리맵 탐색해서 나온 값도 방문
                int finalPosition = ladderSnakeMap.getOrDefault(nextPosition, nextPosition);

                if (visitMap[finalPosition] == -1) {
                    visitMap[finalPosition] = visitMap[nextPosition];
                }
                visitQueue.add(finalPosition);
            }
        }
    }
    System.out.println(visitMap[end]);
}

결론

문제가 주저리 주저리 써져있지만, 잘만 읽어보면 견적을 알 수 있는 문제이다. 이 문제의 핵심은 기본적으로 너비 우선 탐색 (BFS)을 아느냐 그리고 어떻게 해결하는지 아느냐이다. 다만 기본적인 개념에 약간의 향신료(뱀/사다리)가 첨가하여 조건을 다시 생각하게 만드는 문제였다.

이러한 문제 유형이 삼성전자 입사 코딩 테스트 유형이다. 삼성전자라 괜히 쫄지 말고 문제를 잘 분석하고 개본 개념을 잘만 활용하면 면접은 볼 수 있다. 시간은 충분하다. 3시간에 2문제. (2019년까지 그러했는데, 지금은 모르겠다.) 충분히 심사숙고하여 해결할 수 있다. 그렇기에 개념 숙지 및 활용이 중요하다.