[Java/자바 백준 16928] 뱀과 사다리 게임

풀이

우선 최솟값을 위해 BFS를 사용했습니다.

 

1차원 배열을 길이가 100으로 선언하고 0으로 초기화 해줍니다.

해당 인덱스에 사다리나 뱀이 있다면 이동하게되는 위치를 넣어주고

0에서부터 큐에 삽입하여 게임을 시작합시다 !

 

1~6에 주사위에 따라 전진하면서

해당값을 방문했는지, 범위에 벗어나지 않는지, 배열에 사다리, 뱀이 있는지 판단해주며

 

100에 도달시 (배열이라 인덱스는 99입니다)  걸린 시간을 출력해주면 되는 문제 입니다 !

import java.io.*;
import java.util.*;

public class Main{
	static int[] map;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		map = new int[100];
		
		//사다리 
		int N = Integer.parseInt(st.nextToken());
		//뱀 
		int M = Integer.parseInt(st.nextToken());
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			map[start - 1] = end - 1;
		}
		
		for(int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			map[start - 1] = end - 1;
		}
		
		bfs();
		
	}
	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[100];
		
		queue.offer(0);
		visited[0] = true;
		int time = 0;
		while(! queue.isEmpty()) {
			time ++;
			int size = queue.size();
			for(int i = 0 ; i < size ; i++) {				
				int cur = queue.poll();
				for(int plus = 1 ; plus <= 6 ; plus ++) {
					int nx = cur + plus;
					
					if(0 > nx || nx > 99 || visited[nx]) continue;
					// 목적지 도착 할때 
					if(nx == 99) {
						queue.clear();
						System.out.println(time);
						return;
					}
					// 사다리나 뱀이 없을때 
					if(map[nx] == 0) {						
						queue.add(nx);
						visited[nx] = true;
						
					}
					// 사다리나 뱀이 있을때 방문한 값이 아니라면 큐에 삽입  
					else {
						if(visited[map[nx]]) continue;
						queue.add(map[nx]);
						visited[map[nx]] = true;
						
					} 	
				}
			}
		}
	}
}