[백준] 16928번_뱀과 사다리 게임_Java

문제 링크 👉 https://www.acmicpc.net/problem/16928

문제 접근

---

100번 칸에 도착하기 위해 필요한 최소 주사위 굴림 횟수 구하기

• 보드판은 10 * 10 이고, 총 100 칸이다.
• 플레이어는 주사위를 굴려 나온 숫자 만큼 이동한다.

ex) 현재 11번 칸에서 주사위를 굴려 3이 나오면 14번 칸으로 이동한다.

• 주사위를 굴린 결과가 100번 칸을 넘어가면 이동할 수 없다.
• 게임은 1번 칸에서 시작해서 100번 칸으로 이동해야 한다.
• 도착한 칸에 사다리가 있으면 사다리를 타고 올라간다. ex) 34번 칸에 도착했을 때 52번 칸으로 이동하는 사다리가 있다면 52번 칸으로 이동한다.
  
• 도착한 칸에 뱀이 있으면 뱀을 타고 내려간다. ex) 21번 칸에 도착했을 때 1번 칸으로 이동하는 뱀이 있다면 1번 칸으로 이동한다.
  

해결 방식

---

BFS를 사용하여 문제를 해결해야 한다.

• 입력

  1. 게임판에 있는 사다리 수 n 과 뱀의 수 m 이 주어진다.

  2. 사다리의 정보 x , y 가 주어진다. (x 에 도착하면 y 로 이동)

  3. 뱀의 정보 u, v 가 주어진다. (u 에 도착하면 v 로 이동)

     사다리와 뱀의 정보는 HashMap 에 저장한다. 도착 좌표를 key , 이동 좌표를 value 로 저장하여 이동 정보를 찾을 수 있도록 한다.

• BFS 실행
  1. 1번 칸에서 이동할 경우의 수를 모두 구한다.
     1. 2 ~ 7번 칸까지 이동할 수 있으며 각 칸에 사다리 또는 뱀이 있는지 확인한다.
     2. 사다리, 뱀이 없으면 각 칸과 주사위 굴린 횟수를 Queue 에 저장하고 주사위 굴린 횟수를 저장하는 dist 에 1을 저장한다.
  2. q.isEmpty() 가 false 일 동안 실행한다.
     1. q.poll 하여 현재 위치와 그 위치에 있기 위해 굴린 주사위 횟수를 curr 배열에 저장한다.
     2. 주사위 수 1부터 6까지 순회한다.
        • 현재 칸 curr[1] 에 주사위 수 i를 더하여 next 에 저장한다.
        • next 가 100보다 크거나 같으면 continue
        • next 칸에 사다리나 뱀이 있는지 확인한다.
        • 사다리나 뱀이 없으면 Queue 에 이동 칸과 주사위 굴린 횟수를 저장한다.
          이 때 주사위 굴린 횟수가 이동 예정 칸의 최소 주사위 굴림 횟수보다 작을 때만 이동할 수 있도록 한다.

          ```jsx
          else if (curr[1] + 1 < dist[next / 10][next % 10]) {
          				q.offer(new int[]{next, curr[1] + 1});
                  dist[next / 10][next % 10] = curr[1] + 1;
          }
          
          ```

  3. 사다리나 뱀이 있는 경우에는 moving 메소드를 호출한다

     1. 사다리가 있는 경우 ladder , curr 를 파라미터로, 뱀이 있는 경우에는 snake , curr 를 파라미터로 전달한다.

     2. map.get(curr[0]) 하여 사다리 또는 뱀을 통해 이동하는 칸을 가져와 moved 에 저장한다.

     3. 이동할 칸의 누적 굴림 횟수와 현재까지의 누적 굴림 횟수를 비교했을 때 현재까지의 누적 굴림 횟수가 작을 때 Queue 에 저장 및 dist 를 업데이트 한다.

         if (dist[row][col] > curr[1] + 1) {
                    dist[curr[0] / 10][curr[0] % 10] = curr[1] + 1;
                    dist[row][col] = curr[1] + 1;
                    q.offer(new int[]{moved, curr[1] + 1});
          }

  4. while 문이 종료되면 dist[9][9] 를 프린트 하여 정답을 도출한다.

구현 코드

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

public class Main {
    static int[][] map;
    static int[][] dist;
    static Map<Integer, Integer> ladder;
    static Map<Integer, Integer> snake;
    static Queue<int[]> q;

    public static void moving(Map<Integer, Integer> map, int[] curr) {
        int moved = map.get(curr[0]);
        int row = moved / 10;
        int col = moved % 10;

        if (dist[row][col] > curr[1] + 1) {
            dist[curr[0] / 10][curr[0] % 10] = curr[1] + 1;
            dist[row][col] = curr[1] + 1;
            q.offer(new int[]{moved, curr[1] + 1});
        }
    }

    public static void bfs() {
        q = new LinkedList<>();
        dist[0][0] = 0;
        for (int i = 1; i <= 6; i++) {
            if (ladder.containsKey(i)) {
                moving(ladder, new int[]{i, 0});
            } else if (snake.containsKey(i)) {
                moving(snake, new int[]{i, 0});
            } else {
                q.offer(new int[]{i, 1});
                dist[0][i] = 1;
            }
        }

        while (!q.isEmpty()) {
            int[] curr = q.poll();

            for (int i = 1; i <= 6; i++) {
                int next = curr[0] + i;

                if (next >= 100) continue;

                if (ladder.containsKey(next)) {
                    moving(ladder, new int[]{next, curr[1]});
                } else if (snake.containsKey(next)) {
                    moving(snake, new int[]{next, curr[1]});
                } else if (curr[1] + 1 < dist[next / 10][next % 10]) {
                    q.offer(new int[]{next, curr[1] + 1});
                    dist[next / 10][next % 10] = curr[1] + 1;
                }
            }
        }
    }

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

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]); // 사다리 수
        int m = Integer.parseInt(input[1]); // 뱀의 수
        map = new int[10][10];
        dist = new int[10][10];
        ladder = new HashMap<>();
        snake = new HashMap<>();

        for (int i = 0; i < 10; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            ladder.put(Integer.parseInt(input[0]) - 1, Integer.parseInt(input[1]) - 1);
        }

        for (int j = 0; j < m; j++) {
            input = br.readLine().split(" ");
            ladder.put(Integer.parseInt(input[0]) - 1, Integer.parseInt(input[1]) - 1);
        }

        bfs();
        System.out.println(dist[9][9]);
    }
}

마무리

풀이 방향을 잡는건 문제를 읽자마자 바로 떠올릴 수 있었다. 다만 풀이과정에서 자잘하게 잘 못 설계한 부분이 있어서 완전히 풀어내는데까지는 시간이 조금 걸렸다.
이제 개념을 잘 이해하고 있다고 생각하는 자료구조의 골드 레벨 문제는 접근을 잘 할 수 있을 것 같고, 문제만 좀 더 잘 읽으면 풀이도 금방 해낼 수 있을거란 자신감이 생긴것 같다.