뱀과 사디리 게임 - 16928번

---

풀이 방법

bfs를 이용해서 최단 경로를 구해주었다. 현재 위치와 위치에 도달하기까지 굴린 주사위 횟수를 가진 클래스를 만들어 주었다. map에는 뱀과 사다리 경로를 넣어주었는데 굳이 따로 나눌 필요없이 한번에 넣어주었다. 판의 크기가 100으로 고정된것이 아니기 때문에 배열을 이용해서 boolean을 체크해서 방문된 곳을 확인하는 것보다는 set을 이용해서 방문했던 위치를 확인해 주었다.

 

내 코드

package com.company;

import java.io.*;
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());
        HashSet<Integer> set  = new HashSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < N + M; i++) {
            st = new StringTokenizer(br.readLine());
            int key = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            map.put(key, value);
        }

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0));
        set.add(1);

        while (!q.isEmpty()) {
            Node current = q.poll();

            if(current.getIndex() == 100){
                System.out.println(current.getCount());
                break;
            }

            for (int i = 1; i <= 6; i++) {
                int index = map.getOrDefault(current.getIndex() + i, current.getIndex() + i);
                if(set.contains(index))
                    continue;
                set.add(index);
                q.add(new Node(index, current.getCount() + 1));
            }
        }
    }
}

class Node {
    private int index;
    private int count;

    Node(int index, int count) {
        this.index = index;
        this.count = count;
    }

    public int getIndex() {
        return index;
    }

    public int getCount() {
        return count;
    }
}