문제 정리

---

주사위(1~6)을 이용해 보드판의 1에서 100까지 최소 몇 번 굴려야 하는지 구해야 한다
보드판에는 뱀과 사다리가 있는데
뱀은 높은 숫자에서 낮은 숫자로,
사다리는 낮은 숫자에서 높은 숫자로 건너뛸 수 있다

주사위를 굴릴 때 마다
주사위 눈금 + 현재 있는 보드판의 숫자
만큼 이동한다

입력

사다리 수 뱀의 수
사다리 정보 한 줄에 하나씩-> 시작 끝
뱀의 정보 한 줄에 하나씩 -> 시작 끝

출력

최소 라운드 수
(주사위 한 번 굴리는 게 한 라운드)

idea 정리

---

뱀, 사다리 정보는 O(1)으로 접근할 수 있도록 hashmap을 이용한다
bfs 자체는 간단히 이동 수 계산, 뱀이나 사다리가 있는지 확인해서 queue에 넣어주면 된다

여기서 조심해야 할 것은
bfs의 visited 처리인데
같은 칸에 사다리, 뱀 둘 다 가진 경우는 없지만 사다리, 뱀의 도착지점은 같을 수 있기 때문에
사다리와 뱀의 도착지점은 visited 처리를 하면 안된다

이 문제를 그래프 탐색으로 보려면
각 정점은 특정 지점에서 주사위로 갈 수 있는 지점이다

알고리즘 정리

---

1. 뱀, 사다리 정보는 hashmap에 넣어준다
2. bfs는 보드칸의 1부터 시작해서 주사위 1~6 각각의 경우를 계산해 연결 지점으로 보고 queue에 넣는다
   -> 만약 뱀이나 사다리의 시작점을 만나면 주사위 눈금 결과가 아니라 도착 지점을 queue에 넣어준다
3. 100이 나올때까지 2번 반복

구현

---

//뱀과 사다리 게임
public class Main {
	static int N, M, res;
	static int start=1, end=100;
	static boolean[] visited;
	static Map<Integer, Integer> gameThings;		//뱀과 사다리 -> x,y
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visited = new boolean[101];		//1~100
		gameThings = new HashMap<>();
		
		for(int i=0; i<N; i++) {		//사다리
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			gameThings.put(x, y);
		}
		
		for(int i=0; i<M; i++) {	//뱀
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			gameThings.put(x, y);
		}
		
		bfs();
		bw.write(res + "");
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			res++;
			for(int i=0,qSize=q.size(); i<qSize; i++) {
				int now = q.poll();
				
				for(int j=1; j<=6; j++) {		//주사위값 계산
					int move = now + j;
					if(move==end) return;
					
					if(move > end) continue;
					if(visited[move]) continue;
					
					visited[move] = true;
					if(gameThings.containsKey(move)) {		//뱀, 사다리를 만남
						move = gameThings.get(move);
					}
					q.add(move);
				}
			}
		}//end of while
	}
}

결과

---