뱀과 사다리 게임

📍 문제 설명

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

💡 접근

1번에서 100번으로 가는데 사다리면 앞으로 뱀이면 뒤로가게 하면된다.

 

👩‍💻 코드

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

public class Main {
    static int x,y;
    static HashMap<Integer, Integer> ladder, snake;
    static boolean[] visited = new boolean[101];
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        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()); // 뱀 위치 정보

        ladder = new HashMap<>();
        snake = new HashMap<>();

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            ladder.put(x, y);
        }
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            snake.put(x, y);
        }

        System.out.println(T.solution(1));
    }

    private int solution(int n) {
        Queue<Integer> q = new LinkedList<>();
        //시작 지점 큐에 넣기
        q.offer(n);
        visited[n] = true;

        //주사위 굴린 횟수
        int cnt = 0;
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                int cx = q.poll();
                if(cx == 100) return cnt;
                for(int j = 1; j <= 6; j++) {
                    //사다리나 뱀 있는 칸이면 그 칸으로 이동
                    int nx = cx + j;
                    if(nx > 100 || visited[nx]) continue;
                    visited[nx] = true;
                    if(ladder.containsKey(nx)) {
                        nx = ladder.get(nx);
                        visited[nx] = true;
                    }
                    if(snake.containsKey(nx)) {
                        nx = snake.get(nx);
                        visited[nx] = true;
                    }
                    q.offer(nx);
                }
            }
            cnt++;
        }
        return 0;
    }
}