[BaekJoon] 16928 뱀과 사다리 게임 (Java)

1.  문제 링크

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

2.  문제

요약

• 뱀과 사다리 게임은 정육면체 주사위를 사용하고, 각 면에는 1부터 6까지의 수가 하나씩 적혀 있습니다.
• 게임은 크기가 10x10인 보드판에서 진행되고, 각 칸에는 1부터 100까지의 수가 하나씩 순서대로 적혀져 있습니다.
• 플레이어는 주사위를 굴려 나온 수만큼 이동해야 합니다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 더이상 이동할 수 없습니다.
• 도착한 칸이 사다리면, 사다리를 타고 위로 올라가고, 뱀이 있는 칸에 도착하면, 뱀을 따라서 아래로 내려가게 됩니다.
• 게임의 목표는 1번 칸에서 시작하여 100번 칸에 도착하는 것입니다.
• 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구하는 문제입니다.
• 입력
  • 첫 번째 줄에 1보다 크거나 같고 15보다 작거나 같은 사다리의 수 N과 1보다 크거나 같고 15보다 작거나 같은 밤의 수 M이 주어집니다.
  • 두 번째 줄부터 N개의 줄에는 x < y인 사다리의 정보를 의미하는 x, y가 주어집니다.
    • x번 칸에 도착하면, y번 칸으로 이동한다는 의미입니다.
  • 다음 M개의 줄에는 u > v인 뱀의 정보를 의미하는 u, v가 주어집니다.
    • u번 칸에 도착하면 v번 칸으로 이동한다는 의미입니다.
  • 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니고, 모든 칸에 대해서 동시에 뱀과 사다리를 모두 가지고 있는 경우는 없습니다.
• 출력: 첫 번째 줄에 100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[] equipments;
	static int[] count;
	boolean[] visited;
	public void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(1);
		visited[1] = true;
		while(!queue.isEmpty()) {
			int cur_position = queue.poll();
			if(cur_position == 100) {
				break;
			}
			for(int i = 1; i < 7; i++) {
				int position = cur_position + i;
				if(position > 0 && position <= 100 && !visited[position]) {
					visited[position] = true;
					if(equipments[position] != 0) {
						if(!visited[equipments[position]]) {
							queue.offer(equipments[position]);
							visited[equipments[position]] = true;
							count[equipments[position]] = count[cur_position] + 1;
						}
					} else {
						queue.offer(position);
						count[position] = count[cur_position] + 1;
					}
				}
			}
		}
	}
	
	public void getMinCount() {
		visited = new boolean[101];
		count = new int[101];
		bfs();
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int ladder_num = Integer.parseInt(input[0]);
		int snake_num = Integer.parseInt(input[1]);
		equipments = new int[101];
		for(int i = 0; i < ladder_num + snake_num; i++) {
			input = br.readLine().split(" ");
			equipments[Integer.parseInt(input[0])] = Integer.parseInt(input[1]);
		}
		br.close();
		Main m = new Main();
		m.getMinCount();
		bw.write(count[100] + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 뱀이나 사다리가 있는 칸에 도착하면 또 다른 칸으로 이동하므로 이를 배열 equipments로 관리합니다.
• 각 칸들을 방문했는지를 나타내는 배열 visited를 생성하고 1번 칸부터 시작하기 때문에 1번 칸만 true로, 나머지 칸은 false로 시작합니다.
• 주사위를 굴려서 1부터 6까지 6개의 값이 나오므로 해당 칸에서 6가지의 경우의 수로 이동할 수 있습니다.
• 해당 칸에서 6가지의 경우로 이동하면서 이동한 칸이 뱀 또는 사다리에 해당하는 칸이라면 다른 칸으로 이동하고, 그렇지 않다면 이동한 칸까지만 이동합니다.
• 각 칸까지 주사위를 굴린 횟수를 나타내는 배열 count를 생성하고 주사위를 굴려 이동할 때, 이동하기 전의 칸에 해당하는 count의 값에 1을 더해준 값을 이동한 칸에 해당하는 count의 값으로 합니다.

public void bfs() {
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.offer(1);
	visited[1] = true;
	while(!queue.isEmpty()) {
		int cur_position = queue.poll();
		if(cur_position == 100) {
			break;
		}
		for(int i = 1; i < 7; i++) {
			int position = cur_position + i;
			if(position > 0 && position <= 100 && !visited[position]) {
				visited[position] = true;
				if(equipments[position] != 0) {
					if(!visited[equipments[position]]) {
						queue.offer(equipments[position]);
						visited[equipments[position]] = true;
						count[equipments[position]] = count[cur_position] + 1;
					}
				} else {
					queue.offer(position);
					count[position] = count[cur_position] + 1;
				}
			}
		}
	}
}

1. 주어진 사다리와 뱀의 정보를 배열 equipments에 저장합니다.
2. 각 칸을 방문했는지를 나타내는 배열 visited와 각 칸까지 이동하는 데에 굴린 주사위 횟수를 나타내는 배열 count를 생성합니다.
3. BFS를 통해 100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지를 구합니다.
   1. BFS 탐색 시에 탐색할 위치를 나타내는 Queue를 생성하고 1번 칸부터 시작하기 때문에 1을 Queue에 넣어주며 1번 칸의 visited 값을 true로 변경합니다.
   2. Queue가 비워지기 전까지 반복문을 돌며 주사위를 최소 몇 번 굴려야 하는지 구합니다.
      1. Queue에서 현재 탐색할 위치를 뽑아내어 변수 cur_position에 넣어줍니다.
      2. 만약 cur_position이 100이라면, 100번 칸에 도착한 것이므로 반복문을 종료합니다.
      3. 현재 칸에서 1부터 6까지만큼 이동할 수 있으므로 1부터 6까지 반복문을 돌며 칸을 이동합니다.
         1. 현재 위치에서 주사위의 눈금만큼 이동한 칸을 변수 position에 넣어줍니다.
         2. 만약 이동한 칸이 보드판 내에 위치하고 아직 방문되지 않았다면
            1. 이동한 칸의 visited 값을 true로 변경합니다.
            2. 만약 이동한 칸이 사다리 또는 뱀에 해당하는 칸이라면, 사다리 또는 뱀을 통해 이동한 칸이 아직 방문되지 않은 칸이라면 해당 칸을 Queue에 넣고 해당 칸의 visited 값을 true로 변경하며 해당 칸의 count 값을 이동하기 전의 count 값에 1을 더한 값으로 설정합니다.
            3. 만약 이동한 칸이 사다리 또는 뱀에 해당하지 않는 칸이라면, 해당 칸을 Queue에 넣고 해당 칸의 count 값을 이동하기 전의 count 값에 1을 더한 값으로 설정합니다.
4. 3번의 작업이 모두 끝난 후에 100번 칸의 count 값을 출력합니다.