[Java] 백준 16928번: 뱀과 사다리 게임

[문제 바로 가기] - 뱀과 사다리 게임

💡 접근 방식

먼저 BFS로 풀이하는 문제임을 알았음에도 도저히 어떻게 풀어야 할지 감히 잡히지 않아 풀이를 참고했다.

먼저 좌표가 적힌 1차원 배열 board를 선언한다. board의 값들은 좌표 값과 같지만, 아래와 같이 사다리의 시작점에 해당하는 부분에는 사다리 도착점을, 뱀의 꼬리에 해당하는 부분에는 뱀의 머리 좌표를 넣어준다.

사다리 : 32 62 라면 board[32] = 62
뱀 : 95 13 이면 board[95] = 13

이후 1부터 시작하므로 Queue에 1을 넣고 방문 체크 겸 횟수 저장 배열인 count 배열에 count[1] = 0으로 선언해준다.
주사위를 굴려서 나올 수 있는 1부터 6까지 queue.poll()한 값을 꺼내서 더하는데 이때 count[board[newNum]]이 0이 아니면 이미 방문했다는 뜻이므로 넘어간다. 아직 방문하지 않았으면 Queue에 board[newNum] 값을 넣어주고 count[board[newNum]] 값은 count[cur] + 1 해준다.

이와 같이 반복해주면 count[100]에 최소 몇 번만에 보드의 끝까지 갈 수 있는지 값이 적힌다.

풀이

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번 뱀과 사다리 게임 
 * - 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 board[] = new int[101];
		
		for (int i = 1; i <= 100; i++) {
			board[i] = i;
		}
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			board[x] = y;
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			board[x] = y;
		}
		
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(1);
		
		int count[] = new int[101];
		count[1] = 0;
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			
			for (int i = 1; i <= 6; i++) {
				int newNum = cur + i;
				
				if (newNum > 100) continue;
				
				if (count[board[newNum]] == 0) {
					queue.add(board[newNum]);
					count[board[newNum]] = count[cur] + 1;
				}
				
				if (board[newNum] == 100) {
					System.out.println(count[100]);
					return;
				}
			}
		}
	}
}