[백준/16928] 뱀과 사다리 게임 - JAVA

📌 문제

알고리즘 분류 : 그래프, BFS
난이도 : 골드5
출처 : 백준 - 뱀과 사다리 게임

🦧 문제 풀이 접근

gameBorad 배열을 선언 후 BFS를 통해 1~6칸 전진한 후 상황을 Queue에 넣는다.
Queue에서 poll한 위치에서 해당 과정을 반복하면서 100번째 칸에 도착했을때에 얼마나 걸렸는지를 측정한다.

💻 code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Map<Integer,Integer> ladderMap = new HashMap<>();
        Map<Integer,Integer> snakeMap = new HashMap<>();
        int[] gameBoard = new int[101];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            ladderMap.put(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            snakeMap.put(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
        System.out.println(bfs(ladderMap,snakeMap,gameBoard));
    }

    private static int bfs(Map<Integer, Integer> ladderMap, Map<Integer, Integer> snakeMap, int[] gameBoard) {
        Queue<Integer> posQueue = new LinkedList<>();
        posQueue.offer(1);
        while(true) {
            int pos = posQueue.poll();
            for(int i=1;i<=6;i++) {
                int newPos=pos+i;
                if(ladderMap.containsKey(newPos))
                    newPos = ladderMap.get(newPos);
                else if(snakeMap.containsKey(newPos))
                    newPos = snakeMap.get(newPos);
                if(newPos==100) {
                    return gameBoard[pos]+1;
                }
                if(gameBoard[newPos]==0) {
                    gameBoard[newPos] = gameBoard[pos]+1;
                    posQueue.offer(newPos);
                }
                else if(gameBoard[newPos]>gameBoard[pos]+1){
                    gameBoard[newPos] = gameBoard[pos]+1;
                    posQueue.offer(newPos);
                }
            }
        }
    }
}

🥇 결과

🎓 느낀점

DP 같은 느낌으로 배열을 한 칸씩 채워가면서 해결했다. BFS를 통해 빠르게 답을 찾을 수 있었다.