16928_뱀과 사다리 게임

사용 알고리즘: bfs + 메모이제이션

사용 언어: java

 

package week21;

import java.util.*;
import java.io.*;

public class Main_bj_16928_뱀과사다리게임 {
	static int lCnt, sCnt;
	static int[] list = new int[101];
	static int[] dp = new int[101];

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		lCnt = sc.nextInt(); //사다리 개수
		sCnt = sc.nextInt(); //뱀 개수
		for(int i=0; i<lCnt+sCnt; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			list[a] = b; //단방향
		}
		Arrays.fill(dp,  Integer.MAX_VALUE);
		
		System.out.println(play_snake_ladder());
		
	}

	private static int play_snake_ladder() {
		Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); //움직인 수가 작은 순으로 나열
		pq.add(new int[] {1, 0}); //시작점, 움직인횟수
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			
			if(cur[0] == 100) {
				return cur[1];
			}
			
			for(int dice=1; dice<=6; dice++) {
				int nxt = snakeLadder(cur[0] + dice);
				
				if(nxt == 100) { //방어 코드
					return cur[1] + 1;
				}
				
				if(dp[nxt] > cur[1]+1) {
					dp[nxt] = cur[1]+1;
					pq.add(new int[] {nxt, cur[1]+1});
				}
			}
		}
		
		return -1;
	}
	
	private static int snakeLadder(int cur) {
		boolean canStop = false;
		while(!canStop) {
			if(list[cur] == 0) {
				canStop = true;
				continue;
			}
			
			cur = list[cur];
		}
		return cur;
	}

}

 

 

오랜만에 풀어본 백준 bfs...

이 정도면 효율 좋게 잘 짰다고 생각하는데 다른 사람들은 어떻게 짰을까

 

100 넘어가면 움직이지 않는다는 조건을 빼먹었다!! 그런데 정답으로 채점되었다..

어짜피 최소를 찾는 거라서 거기까지 가지 않는 것인가...