[BJ] 16928 : 뱀과 사다리

       문제 요약        

- 문제

- 보드판의 위치 i는 i+1, i+2 ... i+6 와 인접

- 추가적으로, 위치 i가 뱀, 사다리의 시작점인 경우 해당 Item의 끝점과 인접

- 1에서 출발하여 100에 도착 (100을 초과할 수 없음)

- 주사위를 굴러야 하는 횟수의 최솟값

 

- 입출력

 

         아이디어        

 

처음에 위치 i와 연결된 모든 칸을 표현하고 있는 인접 리스트를 구현해서, bfs 를 진행하고자 했다.

하지만, 이 경우, 모든 연결 정보를 표현해버리기 때문에 해당 간선이 뱀이나 사다리인지 확인할 수 없다는 단점이 있었다.

 

- 뱀/사다리 간선을 일반 간선과 구분해야하는 이유

다음 위치에서 뱀/사다리를 사용하여 바로 다다음 곳으로 간다면, 큐에 다음 위치를 넣는 것이 아니라 다다음 위치를 넣어야 하기 때문이다.

(이를 구분하지 않으면, 기본 테스트케이스에서 항상 +1 된 값을 얻게 된다.)

 

- 따라서, 사다리/뱀 간선을 따로 구분하기 위해 Map 자료구조를 사용하였다. 

 

         소스코드        

 

 

package study._0305;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class B16928 { // 뱀과 사다리 게임
    static int N, M; // 사다리의 수, 뱀의 수
    static Map<Integer, Integer> items;
    static int minCnt = Integer.MAX_VALUE;

    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()); // 뱀의 수
        items = new HashMap<>();

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 사다리 정보 : x번 칸 -> y번 칸
            int y = Integer.parseInt(st.nextToken());
            items.put(x, y);
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()); // 뱀의 정보 : u -> v
            int v = Integer.parseInt(st.nextToken());
            items.put(u, v);
        }
        bfs(1); // 1 -> 100
        System.out.println(minCnt);
    }


    private static void bfs(int start) {
        boolean[] visited = new boolean[101]; // 1 ~ 100
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{start, 0});
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            if (now[0] == 100) { // 끝점에 도착
                minCnt = Math.min(minCnt, now[1]);
                return;
            }
            for (int w = 1; w <= 6; w++) { // 현재와 연결되어있는 노드 : next+1,... next+6
                int next = now[0] + w;
                if (next >= 101 || visited[next]) continue;

                if (items.containsKey(next)) { // 사다리 ,뱀
                    visited[next] = true;
                    next = items.get(next); // 사다리나 뱀을 타고 올라간 경우
                }

                visited[next] = true; 
                queue.add(new int[]{next, now[1] + 1});
            }
        }
    }



}