[백준 12851번] 숨바꼭질2 / Java

[boj 12851번] 숨바꼭질2

 

 

현재 index까지 올 수 있는 방법이 몇개있는지 담는 cnt[index]배열이 필요하다.

check[index] = true 임에도 next위치에 가는 경로가 최단이면 cnt를 늘려주어야 한다.

아직 방문하지 않은 상태

이미 방문 했더라도 이동거리가 같은 경우

dist[next] = dist[now] +1 이라면 queue에 넣어주면 된다.

 

 

 

 

public class Main {
	
	static boolean check[] =  new boolean[100001];
	static int cnt[] = new int[100001];
	static int dist[] = new int[100001];
	static int N, K;
	public static void bfs(int N, int K) {
		
		Queue q = new LinkedList();
		
		q.add(N);
		check[N] = true;
		cnt[N] = 1;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			int[] next = {now-1, now+1, now*2};
			for(int n : next){
				if(n >= 0 && n <= 100000) {
					if(!check[n]) {
						check[n] = true;
						dist[n] = dist[now]+1;
						q.add(n);
						cnt[n] = cnt[now];
					}
					else if(dist[n] == dist[now] +1){
						cnt[n] += cnt[now];
					}
				}
			}
		}
		System.out.println(dist[K]);
		System.out.println(cnt[K]);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		bfs(N,K);
	}
}