[백준/JAVA] 16928번: 뱀과 사다리 게임(BFS)

 

 

 

 

문제

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

16928번: 뱀과 사다리 게임

 

 

 

풀이

 

사다리가 있는 위치라면 사다리를 타고 올라갈 위치가 존재하고, 뱀이 있는 위치라면 뱀을 타고 내려갈 위치가 존재한다.

사다리와 뱀이 있는 위치와, 이동할 위치를 해시맵으로 저장한다.

ladder = new HashMap<>(); //사다리와 이동 위치 저장할 해시맵
snake = new HashMap<>();  //뱀과 이동 위치 저장할 해시맵

for(int i = 0; i<n; i++){ //n은 사다리의 개수
    st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());
    ladder.put(x, y);
}

for(int i = 0; i<m; i++){  //m은 뱀의 개수
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    snake.put(u, v);
}

 

 

게임은 주사위를 던져 나온 수만큼 이동한다.

즉, 게임에서 다음 위치(next)는 현재 위치 + 주사위의 수이다. 이 때, 주사위의 수가 1부터 6까지 나올 수 있으므로 경우의 수는 6이다.

다음 위치에 따른 최종 이동 위치는 아래의 경우로 나누어 결정할 수 있다.

 

① next>100인 경우, 이동하지 않고 현재 위치에 머무른다.

② 다음 이동 칸에 사다리 또는 뱀이 있는 경우, 최종 이동 위치는 사다리 또는 뱀을 통해 이동되는 위치이다.

③ next = 100인 경우, 현재까지 주사위를 굴린 수를 출력하고 종료한다.

④ 1≤ next <100인 경우
    -  최종 이동 위치를 방문한 적이 없다면(visited가 0이라면)
    - 최종 이동 위치의 visited값이 현재 visited보다 2이상 크다면(현재 visited 값에서 +1한 값이 원래의 값보다 작아 최솟값인 경우)

최종 이동 위치의 visited 값을 현재 위치(x)의 visited 값에 +1한 값으로 저장한다(최솟값으로 저장하기 위함).
그리고, 큐에 next를 넣는다.


※②와 ③을 확인하는 순서는 절대 바뀌어서는 안된다. ②의 과정을 통해 최종 이동 위치가 결정되기 때문이다.

 

 

 

 

코드

 

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

public class Main {
    private static HashMap<Integer, Integer> ladder;
    private static HashMap<Integer, Integer> snake;

    private static void BFS(){
        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[101];

        q.offer(1);
        visited[1] = 1;

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

            for(int i = 0; i<6; i++){
                int next = current + i+1;

                if(next>100) continue;

                if(ladder.containsKey(next)){
                    next = ladder.get(next);
                }else if(snake.containsKey(next)){
                    next = snake.get(next);
                }

                if(next == 100){
                    System.out.println(visited[current]);
                    return;
                }

                if(next>=1 && next<100){
                    if(visited[next] ==0 | visited[current]+1<visited[next]){
                        visited[next] = visited[current]+1;
                        q.offer(next);
                    }
                }
            }
        }
    }
    
    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());
        ladder = new HashMap<>();
        snake = new HashMap<>();

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

        for(int i = 0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            snake.put(u, v);
        }

        BFS();
    }
}