28. 16928번 뱀과 사다리 게임

 

주사위를 굴려 도착한 칸이 사다리면 사다리를 이용해 올라가고

뱀이 있는 칸이면 뱀을 따라서 내려간다.

이동하기 때문에 배열로 저장한다

 

또한 방문했던 칸은 다시방문하지 못하도록 boolean 배열을 사용해 막는다

- EX) 3 -> 9 -> 12 -> 8 -> 9 -> 12 ->..... 와 같은 식으로 무한히 빠져버릴 수 있기 때문

 

주사위의 눈은 1~6으로 앞의 6칸으로 이동할 수 있다.

6가지의 경우의 수를 모두 돌리는데 이때 도착지점이 사다리나 뱀일경우 해당 지점으로 이동하며

아니면 주사위의 눈만큼 위치를 이동시킨다.

 

이후 100에 도달했을때의 주사위 굴린 수를 호출한다.

 

이를 bfs로 코드로 만들어보자 설명은 주석으로 하겠다

 

static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;

        while(!queue.isEmpty()) {
            int start = queue.poll();

            if(start == 100){
                System.out.println(map[start]);
                return;
            }
            for(int dice=1; dice<=6; dice++){
                int position = start + dice;
                //100 을넘으면 이동 불가
                if(100 < position){
                    continue;
                }
                //이미 방문한 곳 가지못한다
                if(visited[position]){
                    continue;
                }
                visited[position] = true;             
                //주사위를 굴려 이동한위치에 사다리나 뱀이 있을경우
                if(move[position] !=0){                   
                    if(!visited[move[position]]){
                        queue.offer(move[position]);
                        visited[move[position]] = true;
                        map[move[position]] = map[start] +1;
                    }                    
                }else{ //사다리나 뱀이 아닐경우
                    queue.offer(position);
                    map[position] = map[start] + 1;
                }
            }

        }
    }

 

탐색할 bfs 메소드가 만들어졌으니 입력방법만 넣어주면 끝

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


public class training {
        //지도
	public static int[] map = new int[101];
        //뱀과 사다리
	public static int[] move = new int[101];
        //방문한지 안한지를 판별하기위한 불린배열
	public static boolean[] visited = new boolean[101];
    
	public static void main(String[] args) throws Exception {
		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()); //뱀의 수
		
		
		for(int i = 0; i<N+M; i++) {
			st = new StringTokenizer(br.readLine());
			int recent = Integer.parseInt(st.nextToken());
			int after = Integer.parseInt(st.nextToken());
			
			move[recent] = after;
			//뱀,사다리 입력 recent , 출력 after
		}

		bfs();

	}

 

코드 전문

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


public class training {
    //지도
	public static int[] map = new int[101];
    //뱀과 사다리
	public static int[] move = new int[101];
    //방문한지 안한지를 판별하기위한 불린배열
	public static boolean[] visited = new boolean[101];
    
	public static void main(String[] args) throws Exception {
		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()); //뱀의 수
		
		
		for(int i = 0; i<N+M; i++) {
			st = new StringTokenizer(br.readLine());
			int recent = Integer.parseInt(st.nextToken());
			int after = Integer.parseInt(st.nextToken());
			
			move[recent] = after;
			//뱀,사다리 입력 recent , 출력 after
		}

		bfs();

	}

    static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;

        while(!queue.isEmpty()) {
            int start = queue.poll();

            if(start == 100){
                System.out.println(map[start]);
                return;
            }

            for(int dice=1; dice<=6; dice++){
                int position = start + dice;
                //100 을넘으면 이동 불가
                if(100 < position){
                    continue;
                }
                //이미 방문한 곳 가지못한다
                if(visited[position]){
                    continue;
                }

                visited[position] = true;
                
                //주사위를 굴려 이동한위치가 사다리나 뱀일 경우
                if(move[position] !=0){
                    if(!visited[move[position]]){
                        queue.offer(move[position]);
                        visited[move[position]] = true;
                        map[move[position]] = map[start] +1;
                    }
                    
                }else{ //사다리나 뱀이 아닐경우
                    queue.offer(position);
                    map[position] = map[start] + 1;
                    

                }
            }

        }
    }
}

 

결과