[백준 16928] 뱀과 사다리 게임 (Java)

이 문제는 주사위를 굴려 나온 눈만큼 칸을 이동하며, 뱀이 나오면 더 큰 수가 적인 칸으로 이동하고, 사다리가 나오면 더 작은 수가 적힌 칸으로 이동하는 게임이다. 이때, 100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지를 구하는 문제이다.

문제 조건에서, 각 칸에는 최대 하나의 사다리 또는 뱀이 있다고 했다. 즉, 둘 중 하나 혹은 없는 경우만이 존재한다는 의미이며, 도착한 칸에 뱀또는 사다리가 있다면 이를 무조건 이용해야 한다.

x번 칸에서 다음 위치로 주사위를 최소로 사용하여 이동하는 것이므로 dp로 생각할 수 있다. 하지만, bottom-up방식이든 top-down방식 하나로 풀게되면 사다리를 통해 위로 올라가는 경우를 고려하지 못하게 되므로 큐나 스택에 값을 저장해두었다가 꺼내서 처리해주는 과정이 필요하다. 따라서 이 문제는 BFS혹은 DFS로 접근하는 것이 적절하다.

이를 코드로 작성해보면 아래와 같다.

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

public class Main {
    static Map<Integer, Integer> ladders = new HashMap<>();
    static Map<Integer, Integer> snakes = new HashMap<>();
    static int N, M;
    static int[] distance = new int[101];
    static int[] dice = {1, 2, 3, 4, 5, 6};
    
    static final int NOT_VISITED = Integer.MAX_VALUE;
    static final int DESTINATION = 100;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            ladders.put(x, y);
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
            snakes.put(u, v);
        }
        
        Arrays.fill(distance, NOT_VISITED);
        distance[1] = 0;
        recursive(1);
        
        System.out.println(distance[DESTINATION]);
    }
    
    private static boolean isValid(int x) {
        return x >= 0 && x < distance.length;
    }
    
    private static void recursive(int x) {
        if (ladders.containsKey(x)) {
            int nx = ladders.get(x);
            if (distance[nx] > distance[x]) {
                distance[nx] = distance[x];
                recursive(nx);
            }
            return;
        }
        
        if (snakes.containsKey(x)) {
            int nx = snakes.get(x);
            if (distance[nx] > distance[x]) {
                distance[nx] = distance[x];
                recursive(nx);
            }
            return;
        }
        
        for (int i = 0; i < dice.length; i++) {
            int nx = x + dice[i];
            if (isValid(nx) && distance[nx] > distance[x] + 1) {
                distance[nx] = distance[x] + 1;
                recursive(nx);
            }
        }
        
        return;
    }
}

음... 코드가 너무 절차지향적인 것 같다. 실제 코테에서는 비효율적이겠지만 리팩토링을 진행해보자.

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

public class Main {
    public static void main(String[] args) throws IOException {
        Game game = new Game();
        game.init();
        
        Solution s = new Solution(game);
        s.init();
        s.solve(1);
        
        game.over();
    }
    
    static class Game {
        private final Map<Integer, Integer> ladders = new HashMap<>();
        private final Map<Integer, Integer> snakes = new HashMap<>();
        private final int[] dice = {1, 2, 3, 4, 5, 6};
        
        public void init() throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
            
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
                ladders.put(x, y);
            }
            
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
                snakes.put(u, v);
            }
        }
        
        public List<Integer> next(int x) {
            List<Integer> res = new ArrayList<>();
            if (ladders.containsKey(x)) {
                res.add(ladders.get(x));
                return res;
            }
            
            if (snakes.containsKey(x)) {
                res.add(snakes.get(x));
                return res;
            }
            
            for (int i = 0; i < dice.length; i++) {
                res.add(x + dice[i]);
            }
            return res;
        }
        
        public void over(Solution s) {
        	int[] distance = s.getDistance();
            System.out.println(distance[DESTINATION]);
        }
    }
    
    static class Solution {
        public static final int NOT_VISITED = Integer.MAX_VALUE;
        public static final int DESTINATION = 100;
        
        private final Game game;
        private final int[] distance = new int[101];
        
        public Solution(Game game) {
            this.game = game;
        }
    
        public void init() {
            Arrays.fill(distance, NOT_VISITED);
            distance[1] = 0;
        }
        
        public void solve(int x) {
            List<Integer> positions = game.next(x);
            if (positions.size() == 1) {
                int nx = positions.get(0);
                if (distance[nx] > distance[x]) {
                    distance[nx] = distance[x];
                    solve(nx);
                }
                return;
            }
            
            for (int i = 0; i < positions.size(); i++) {
                int nx = positions.get(i);
                if (isValid(nx) && distance[nx] > distance[x] + 1) {
                    distance[nx] = distance[x] + 1;
                    solve(nx);
                }
            }
        }
        
        private static boolean isValid(int x) {
            return x >= 0 && x <= DESTINATION;
        }
        
        public int[] getDistance() {
        	return distance;
        }
    }
}

나름대로 SOLID원칙을 지키려고 노력해봤다... 피드백은 언제나 환영이다.