백준[16928] 뱀과 사다리 게임(JAVA)

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

16928번: 뱀과 사다리 게임

 

BFS 로 간단히 풀 수 있는 문제지만 탐색과정중 뱀이나 사다리를 만나면 아예 다른 칸을 점프를 해야하는

점이 특이해서 가져온 문제이다.

 

주사위를 구려 1~6까지 한번에 바로 진행이 가능하다 이때 진행한 칸이 뱀이나 사다리가 존재한다면 

뱀이나 사다리를 통해 이동된 다른칸에서 탐색을 진행하면 된다.

 

우선 방문처리할 보드, 그리고 뱀,사다리에 대한 정보를 저장할 배열, 그리고 큐에 대한 자원을 선언해준다.

 

	static int[] board = new int[101];
	
	static int[] snake = new int[101];
	
	static int[] queue = new int[100];
	
	static int front,rear;

 

 

다음은 BFS 메소드이다.

 

1~6까지 순회하면서 탐색을 진행하되 뱀이나 사다리에 해당하는 칸이 존재한다면 

해당 칸으로 현재 정점을 바꿔주는 과정을 추가해주도록 한다.

또 100번칸에 해당하는 최단거리가 답이므로 100번째 칸을 방문한 최단거리를 리턴해주도록 한다.

 

	static int bfs() {
		queue[rear++] = 1;
		while(queue[front] != 0) {
			int node = queue[front];
			queue[front++] = 0;
			front%=100;
			for(int i = 1; i < 7; i++) {
				int next = node + i;
				if(next <= 100) {
					if(snake[next] != 0) {
						next = snake[next];
					}
					
					if(board[next] == 0) {
						board[next] = board[node] + 1;
						queue[rear++] = next;
						rear%=100;
					}					
				}
				
			}
		}
		return board[100];
	}

 

 

예제에 대한 답)

 

 

아래는 코드의 전문이다.

 

package boj3;

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

public class Boj16928 {
	
	/*
	 * BFS
	 * 제출 完
	 */
	
	static int[] board = new int[101];
	
	static int[] snake = new int[101];
	
	static int[] queue = new int[100];
	
	static int front,rear;
	
	static int bfs() {
		queue[rear++] = 1;
		while(queue[front] != 0) {
			int node = queue[front];
			queue[front++] = 0;
			front%=100;
			for(int i = 1; i < 7; i++) {
				int next = node + i;
				if(next <= 100) {
					if(snake[next] != 0) {
						next = snake[next];
					}
					
					if(board[next] == 0) {
						board[next] = board[node] + 1;
						queue[rear++] = next;
						rear%=100;
					}					
				}
				
			}
		}
		return board[100];
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		n += Integer.parseInt(st.nextToken());
		
		while(n-- > 0) {
			st = new StringTokenizer(in.readLine()," ");
			int idx = Integer.parseInt(st.nextToken());
			snake[idx] = Integer.parseInt(st.nextToken());
		}
		
		System.out.print(bfs());
	}

}