Skip to content

Latest commit

 

History

History
169 lines (131 loc) · 5.99 KB

bj_16928.md

File metadata and controls

169 lines (131 loc) · 5.99 KB
Raw

16928. 뱀과 사다리 게임

Summary

🙇‍♂️ URL : https://www.acmicpc.net/problem/16928
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

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

public class App {

    static int M, N;
    static int[] next = new int[101];   // 다음 이동 장소
    static int[] dist = new int[101];   // 최소 이동 거리
    

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0; i<next.length; i++) {
            next[i] = i;
            dist[i] = -1;
        }

        // 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. 
        // x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.
        for(int i=0; i<N; i++) {
            String[] ladders = br.readLine().split(" ");
            next[Integer.parseInt(ladders[0])] = Integer.parseInt(ladders[1]);
        }

        // 다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. 
        // u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.
        for(int i=0; i<M; i++) {
            String[] snakes = br.readLine().split(" ");
            next[Integer.parseInt(snakes[0])] = Integer.parseInt(snakes[1]);
        }

        // 게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        dist[1] = 0;

        // 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.
        System.out.println(solution(queue));
    }

    public static int solution(Queue<Integer> queue) {
        
        while(!queue.isEmpty()) {
            int location = queue.poll();
            for(int i=1; i<=6; i++) {
                int nextLocation = location + i;

                // 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다.
                if(nextLocation <= 100) {

                    // 사다리 혹은 뱀이 존재한다면, 해당 위치로 이동
                    // 만약 없다면 자기 자신이 그대로 값이 될 것이다.
                    nextLocation = next[nextLocation];
                    
                    // 아직 방문하지 않은 경우 -> 이동횟수 + 1
                    // BFS -> 가장 먼저 해당 칸을 방문했다 = 가장 적은 횟수로 해당 칸으로 이동했다는 의미
                    if(dist[nextLocation] < 0) {
                        dist[nextLocation] = dist[location] + 1;
                        queue.offer(nextLocation);
                    }
                }
            }
        }

        // 100번째 칸의 이동 횟수를 출력
        return dist[100];
    }
}

How to Approach

1. 문제 핵심, 목표

본 문제의 핵심은 '100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값'을 구하는 것이다.

2. 10 x 10 => 100개의 배열로

이 문제에서는 두 개의 배열을 만들었다.

  • 뱀 또는 사다리의 정보가 적혀있는 배열. 다르게 말하면 "현재에 머물러야 할지, 혹은 한번 더 다른 칸으로 이동해야 하는지 적혀있는" 배열
  • 현재 위치까지 이동한 가장 적은 횟수를 담고 있는 배열
static int[] next = new int[101];   // 다음 이동 장소
static int[] dist = new int[101];   // 최소 이동 거리
...

for(int i=0; i<101; i++) {
    next[i] = i;  
    dist[i] = -1;
}
...
// 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. 
// x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.
for(int i=0; i<N; i++) {
    String[] ladders = br.readLine().split(" ");
    next[Integer.parseInt(ladders[0])] = Integer.parseInt(ladders[1]);
}

// 다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. 
// u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.
for(int i=0; i<M; i++) {
    String[] snakes = br.readLine().split(" ");
    next[Integer.parseInt(snakes[0])] = Integer.parseInt(snakes[1]);
}

예제 입력 1의 예시에 따르면, next 배열은 아래와 같은 구조를 가질 것이다.

- next[32] = 62
- next[42] = 68
...
- next[95] = 13
...
- next[75] = 19
...

3. BFS 사용

최소 거리를 구한다는 것은 무조건 BFS를 사용하라는 의미로 보면 된다.
처음 시작 값인 1을 큐에 넣어두고, 주사위(1부터 6)를 굴려가며 100까지 이동하는 최단 거리를 찾으면 된다. 단, "100번 칸을 넘어간다면 이동할 수 없다"는 조건이 있기 때문에, 주사위를 굴려 이동한 칸이 100을 넘어가서는 안된다.

...
while(!queue.isEmpty()) {
    int location = queue.poll();
    for(int i=1; i<=6; i++) {
        int nextLocation = location + i;

        // 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다.
        if(nextLocation <= 100) {

            // 사다리 혹은 뱀이 존재한다면, 해당 위치로 이동
            // 만약 없다면 자기 자신이 그대로 값이 될 것이다.
            nextLocation = next[nextLocation];
            
            // 아직 방문하지 않은 경우 -> 이동횟수 + 1
            // BFS -> 가장 먼저 해당 칸을 방문했다 = 가장 적은 횟수로 해당 칸으로 이동했다는 의미
            if(dist[nextLocation] < 0) {
                dist[nextLocation] = dist[location] + 1;
                queue.offer(nextLocation);
            }
        }
    }
}
return dist[100];