16928. 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

문제

뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.

주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

 

입력

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

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

Logic

1. 현재 위치에서 6칸을 이동하면서 방문한 적 없는 곳이면 Queue에 추가한다.
2. Queue에 있는 위치에서 1번 과정을 반복한다.

 

이 문제는 10 x 10 크기의 게임판이라 했지만 결국에는 한 칸씩 이동하며 탐색하는 것이기 때문에

2차원 배열로 만들면 끝에 도달했을 때 다음 줄 처음으로 이동해야 하므로 복잡해진다.

 

그래서 어차피 한 칸씩 이동하며 탐색하는 것이기 때문에 크기 [100]짜리 1차원 배열을 만들어서 풀면 훨씬 간단하게 풀 수 있다.

 

우선 주사위의 최대 숫자는 6이므로 현재 위치에서 앞으로 6칸을 전부 탐색한다.

탐색하면서 방문 처리를 해준다. 그 이유는 뱀을 만났을 땐 뒤로 돌아가는데 그 곳이 이미 방문한 곳이면 갈 필요가 없기 때문이다.

 

탐색을 진행하다가 사다리나 뱀을 만나면 해당 지점으로 이동한다.

 

전체적인 로직은 이게 전부다.

그런데 처음엔 이런 의문이 들었다. [어차피 뱀은 뒤로 돌아가는 거니까 건너 뛰어도 되지 않나?]

이 생각을 가지고 뱀을 건너뛰면 답을 맞출 수 없다. 그 이유를 알아보자.

 

파란 화살표는 사다리고 빨간 화살표는 뱀이라 했을 때,

뱀을 타면 주사위를 5번만 던지면 도착할 수 있지만 뱀을 건너뛰면 11번의 주사위를 던져야 한다.

 

이런 이유로 뱀도 신경 써야한다. (저도 처음에 그냥 신경 안 쓰고 했다가…)

 

아무튼 그래서 코드를 보자면 1차원 배열에 사다리와 뱀을 입력 받는다.

어차피 이동할 위치가 인덱스 이므로 뱀과 사다리를 따로 받을 필요는 없다.

int[] map = new int[101];
    for (int i = 0; i < N + M; i++) {
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        map[s] = e;
}

 

이후 탐색을 진행하면서 해당 위치에서 6칸을 탐색하며 0이상(사다리 또는 뱀)을 만나면 방문 여부를 확인하고 방문한 적이 없으면 위치를 이동 시킨다.

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

    if (next > 100)
        break;

    if (visited[next])
        continue;

    if (map[next] > 0) {
        int p = map[next];

        if(!visited[p])
            q.add(new int[] {p, step+1});

    } else if (map[next] == 0) {
        q.add(new int[] { next, step + 1 });
    }
}

 

CODE

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

/**
 * 백준 16928. 뱀과 사다리 게임 - 골드 5
 * @category BFS
 */
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());

		int[] map = new int[101];
		for (int i = 0; i < N + M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());

			map[s] = e;
		}

		boolean[] visited = new boolean[101];
		Queue<int[]> q = new ArrayDeque<>();

		q.add(new int[] { 1, 0 });

		int min = Integer.MAX_VALUE;
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int posi = cur[0];
			int step = cur[1];
			visited[posi] = true;

			if (posi == 100) {
				min = Math.min(min, step);
				continue;
			}

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

				if (next > 100)
					break;
				
				if (visited[next])
					continue;

				if (map[next] > 0) {
					int p = map[next];
					
					if(!visited[p])
					q.add(new int[] {p, step+1});

				} else if (map[next] == 0) {
					q.add(new int[] { next, step + 1 });
				}
			}
		}
		
		System.out.println(min);
	}
}