백준 16928번 : 뱀과 사다리 게임(Java)

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

16928번: 뱀과 사다리 게임

---

[풀이]

 

- BFS 유형의 문제입니다.
- 사다리 혹은 뱀이 있는 곳에 대한 값을 배열에 저장합니다.
- 이렇게 값을 받은 배열은 BFS 메소드 내부에서 다음 위치로 이동할 때 사용하게 됩니다.
- BFS 메소드 내부에서 유의할 점은 100이 넘지 않아야 한다는 것입니다. 그렇기에, 100을 넘지 않는다는 조건문을 추가해서 Queue에 추가해줍니다.
- BFS 메소드를 통해 주사위의 최소 횟수를 구해야 하기에 visited 배열을 통해 방문에 대한 여부를 확인합니다.

 

---

[코드]

 

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

public class Main {
	static int n,m,result;
	static boolean[] visited = new boolean[101];
	static int[] map = new int[101];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		result = 0;
		Arrays.fill(map,0);
		
		for(int i = 0; i< n + m ; i++){
			st = new StringTokenizer(br.readLine()," ");
			map[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
		}
		solve();
	}
	
	public static void solve(){
		Queue<Point> queue = new LinkedList<>();
		queue.offer(new Point(1,0));
		visited[1] = true;
		
		while(!queue.isEmpty()){
			Point poll = queue.poll();
			if(poll.position == 100){
				System.out.println(poll.count);
				return;
			}else{
				for(int i = 1; i<= 6; i++){
					if(poll.position + i <= 100){
						if(!visited[poll.position + i] && map[poll.position + i] == 0){
							queue.offer(new Point(poll.position + i, poll.count + 1));
							visited[poll.position + i] = true;
						}else if(!visited[poll.position + i] && map[poll.position + i] != 0){
							queue.offer(new Point(map[poll.position + i], poll.count + 1));
							visited[map[poll.position + i]] = true;
						}
					}
				}
			}
		}
	}
	
	static class Point{
		int position;
		int count;
		
		public Point(int position, int count) {
			this.position = position;
			this.count = count;
		}
	}
}