문제링크

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

구현방법

뱀과 사다리의 위치를 제대로 파악해서 진행하는게 가장 큰 쟁점이였습니다. 처음에는 단순하게 사다리는 올라가니까 체크 해놓고 올라가야지 하고 뱀은 내려가는데 이건 타면 최소가 될 수 있을까 했습니다. 근데 생각해보니 뱀을 만나서 내려간다음 사다리를 통해서 더 높은 곳을 올라서 가게 되면 최소가 될 수 있다는 생각을 하게 되었습니다.

HashMap만을 이용해서 진행하게 되면 ContainsKey값을 찾는게 꽤 시간이 걸리는 것으로 알고 있어서 HashSet을 통해서 사다리의 시작과 뱀의 시작을 넣어두고 만약 Contains에서 true이면서 방문한적이 없는 경우 방문 체크를 하고 사다리및 뱀 이동을 진행했습니다. -> 이동을 진행시 Pointer 클래스를 통해서 number와 현재까지 이동 횟수를 체크 해둡니다.

어쩌피 100을 초과하는 경우는 이동이 불가능하기 때문에 100을 초과하는 경우에는 continue를 통해서 값을 보냈고 , 현재 위치가 100에 도착했을경우 count값을 answer에 넣어주고 끝내줍니다.

구현알고리즘

너비 우선 탐색 + HashMap

CODE

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

public class Main {



    static HashSet<Integer> start_line = new HashSet<>();
    static HashMap<Integer,Integer> maps = new HashMap<>();

    static HashSet<Integer> start_snake = new HashSet<>();
    static HashMap<Integer,Integer> snake_maps = new HashMap<>();

    public static boolean visited[] = new boolean[101];

    static int answer;
    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());
        //사다리 먼저
        for(int idx = 0; idx < N;idx++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            start_line.add(start);
            maps.put(start,end);
        }
        //뱀 위치 파악
        for(int idx = 0; idx < M;idx++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            start_snake.add(start);
            snake_maps.put(start,end);
        }

        game_Start(1);

        System.out.println(answer);
    }

    private static void game_Start(int start_idx) {
        Queue<Point> que = new LinkedList<>();
        que.offer(new Point(start_idx,0));
        visited[start_idx] = true;
        while(!que.isEmpty()){
            Point cur = que.poll();
            if(cur.number == 100){
                answer= cur.number;
            }

            for(int idx= 1; idx <=6;idx++){
                int next_number = cur.number + idx;

                //100을 넘기는 경우는 pass
                if(next_number > 100 ){
                    continue;
                }

                //사다리가 있는 곳인경우
                if(start_line.contains(next_number) && !visited[next_number]){
                    visited[next_number] = true;
                    visited[maps.get(next_number)] = true;
                    que.offer(new Point(maps.get(next_number),cur.count+1));
                    continue;
                }
                //뱀이있는 경우
                if(start_snake.contains(next_number) && !visited[next_number] ){
                    visited[next_number] = true;
                    visited[snake_maps.get(next_number)] = true;
                    que.offer(new Point(snake_maps.get(next_number), cur.count+1));
                    continue;
                }

                //방문하지 않은 경우
                if(!visited[next_number]) {
                    visited[next_number] = true;
                    que.offer(new Point(next_number, cur.count + 1));
                }

            }
        }
    }
}

class Point{
    int number;
    int count;

    public Point(int number, int count) {
        this.number = number;
        this.count = count;
    }
}