[JAVA 자바] 백준 16928번 : 뱀과 사다리 게임

▶ 문제

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

16928번: 뱀과 사다리 게임

 

▶ 설명

10x10 로 된 보드가 있다. 주사위를 던져 나오는 숫자대로 이동을 할 때 사다리가 나오면 사다리가 인도하는 곳으로 (앞으로) 전진하고, 반대로 뱀이 나오면 후퇴하여야 한다.

 

 

 

예제 1을 살펴보면 3개의 사다리와 7개의 뱀이 주어졌다.

 

 

보드판의 숫자를 1차 배열로 만들기 

사다리와 뱀 게임 보드판을 표 형식으로 그려보았다. 

예제의 입력 대로 32자리에 62를 넣고, 42 자리에 68을 넣어보았다. (노란색:사다리 , 민트색:뱀)

보드 판을 1차 배열로 길게 늘어 뜨리면 다음과 같다. (편의상 인덱스 0은 비워주고 1부터 100 인덱스까지의 배열로 보드판을 구성한다.)

 

(회색: index, 흰색 : value)

인덱스가 12인 위치에 98을 대신 넣는 식으로 배열의 값을 입력 받도록 하였다.

만약 주사위를 던져 12에 도착하면 12가 가진 값인 98번 인덱스로 이동할 것이다.

 

 

 

노드 방문하기 - 방문에 대한 1차 배열 만들기

처음 주사위를 던지면 1~6에 해당하는 숫자가 나올 것이다. 그럼 Queue 에 1~6를 집어 넣도록 한다. 그리고 방문 체크를 위한 배열에 첫번째로 방문했다는 표시를 한다. 

 

 

1이 나왔다면 다음에 이동할 수 있는 곳은 2~7이 될 것이다. 그런데 2~6 인덱스에는 1을 이미 표시 했으므로 7인 곳에만 2를 표시할 수 있게 된다. 그렇게 1~6에서 주사위를 각각 던질 때에는 아래 그림처럼 7~12 칸에 2가 방문 표시 될 것이다. 

그런데 12인덱스에 98로 이동하라고 하였으므로 인덱스 98에 2라는 값을 주도록 한다.

 

 

🎉

98에서 주사위를 던졌을 때 3~6이 나오면 보드에서 빠져나올 수 있으므로 주사위를 총 3번 던졌을 때 이 게임은 끝낼 수 있게 된다.

이를 코드로 옮기면 다음과 같다.

 

 

 

 

▶ 문제 풀이

🌱 풀이.  

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

public class Main {
	static int[] board;

	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());// 뱀

		board = new int[101];
		// 1,2,3,4,...100 자기 인덱스번호를 원소 값으로 하기
		for (int i = 1; i < board.length; i++) {
			board[i] = i;
		}

		while (n-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			board[x] = y;
		}
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			board[x] = y;
		}


		int result = bfs(1);
		System.out.println(result);

	}

	private static int bfs(int startNode) {

		int[] check = new int[101]; // 방문 순서를 기록하기 위한 배열 생성. 
		Queue<Integer> q = new LinkedList<>();
		q.offer(startNode); //처음에 인덱스 1이 들어간다.
		check[startNode] = 0; 

		while (true) {
			int visitedNum = q.poll();
			//주사위 1~6이 나오는 경우를 살피기.
			for (int i = 1; i < 7; i++) {            	
				int newNode = visitedNum + i;
                
                // board의 범위를 넘기면 무시하기
                // - check 배열에 IndexOutOfBoundsException을 발생시킬 수 있기 때문
				if (newNode > 100) { 
					continue;
				}
                
                // check되어있는 경우(방문을 한적이 있는 경우)는 무시한다는 것을 전제로 함.
				if (check[board[newNode]] == 0) { 
					q.offer(board[newNode]);
					check[board[newNode]] = check[visitedNum] + 1;
				}
				if (board[newNode] == 100) {
					return check[100];
				}
			}

		}

	}

}

 

 

 

참고로, 이 코드는 사실 n과 m 을 합쳐서 하나의 반복문으로 만들어도 상관 없다. 

 

 

 

 

▶ Log

이전에 풀었던 BFS 문제로 단련이 되어서 그런지 이 문제는 수월하게 풀 수 있었다.