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

문제보러가기

16928번: 뱀과 사다리 게임

이문제는 탐색 문제로 bfs를 이용해 풀었다. 100까지 갈 때 최소한의 주사위를 던져서 가는 것이므로 bfs라고 분류한 것을 보지 않아도 bfs임을 유추할 수 있다. 일반 bfs와 다르게 동서남북 방향이 아닌 1~6까지의 숫자로 이동하는 부분만 잘 처리해주면 문제없이 풀 수 있다.

+참고로 메모리 초과가 뜬다면 visited [][]로 체크해주는 부분이 빠졌는지 확인해보자..!! 사실 내가 메모리 초과가 떴었다 바보같이 ㅎ....

 

 

 

문제풀이

-뱀일 경우 내려갈 곳에 대한 정보, 사다리일 경우 올라갈 곳에대한 정보를 저장한다.

->사다리의 아랫부분과 윗부분을 다 저장할 필요가 없다는 뜻. 사다리는 내려오기만 할 뿐 올라가는 경우는 없으므로 윗부분에 토큰이 방문해도 아무 일도 일어나지 않는다. 아래 테스트 예제의 경우를 배열에 표시해보면

3 7

32 62

42 68

12 98

95 13

97 25

93 37

79 27

75 19

49 47

67 17

	98
	62
	68							47
						17
				19				27
		37		13		25

->이런 식으로 배열이 구성된다.

-Token클래스를 만들어 현재 방문한 배열의 숫자와 현재까지 주사위 굴린 횟수를 저장하며 갱신한다.

-배열의 인덱스가 아닌 숫자를 저장하는 것은 1~6칸을 이동했을 때 계산을 쉽게 하기 위함이다.

ex) 6에서 주사위 6이 나왔을 경우 12 -> 인덱스로 변환하면 [1][1]이 된다.(이 부분 다른 분들은 어떻게 했는지 봐야겠다)

int num = token.num+i; // i : 1~6
int sx = num>=10 ? num%10==0 ? num/10-1 : num/10 : 0;
int sy = num>=10 ? num%10==0 ? 9 :num%10-1 : num-1;

-탐색을 통해 경우의 수를 구하다가 num==100이 되는 순간 주사위 굴린 횟수를 return 하고 종료한다.

 

 

 

 

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

public class Ex_16928 {
	static int[][] map;
	public static void main(String[] args) throws Exception{
		map = new int[10][10];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int snake = Integer.parseInt(st.nextToken());
		int ladder = Integer.parseInt(st.nextToken());
		
        //뱀과 사다리 각각 이동하는 경우에만 배열에 저장
		for(int i=0;i<snake+ladder;i++) {
			st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			int row = num1>=10 ? num1%10==0 ? num1/10-1 : num1/10 : 0;
			int col = num1>=10 ? num1%10==0 ? 9 :num1%10-1 : num1-1;
			map[row][col] =num2;
			
		}
		System.out.println(bfs(new Token(1,0)));
		
		
		
	}
	static int bfs(Token t) {
		boolean[][] visited = new boolean[map.length][map.length];
		Queue<Token> q = new LinkedList<>();
		q.add(t);
		visited[0][0]=true;
		while(!q.isEmpty()) {
			Token token = q.poll();
            //주사위 숫자만큼 칸수 이동
			for(int i=1;i<=6;i++) {
				int num = token.num+i;
                //숫자를 배열 인덱스로 변환
				int sx = num>=10 ? num%10==0 ? num/10-1 : num/10 : 0;
				int sy = num>=10 ? num%10==0 ? 9 :num%10-1 : num-1;
				if(sx < 0  || sy < 0 || sx >=map.length || sy >= map.length) {
					continue;
				}
				if(visited[sx][sy]) {
					continue;
				}
                //100번째칸을 만나게되면 종료
				if(num==100)
					return token.cnt+1;
                //0이 아닌경우 즉, 사다리이거나 뱀이여서 이동해야하는 경우
				if(map[sx][sy]!=0) {
					num=map[sx][sy];
				}
				visited[sx][sy]=true;
				q.add(new Token(num,token.cnt+1));
				
			}
		}
		return 0;
	}

}
class Token{

	int cnt;
	int num;
	Token(int num,int cnt){

		this.cnt = cnt;
		this.num = num;
	}
}