[백준 3주차 - 12851] 숨바꼭질2 (Java)

📌 문제

 

📝 풀이과정

1. 가장 빠른 시간으로 동생으로 가는 시간 → 최단거리 문제이므로  BFS 로 푼다

- 3개의 방향으로 갈 수 있음 (x-1, x+1, 2*x)

- visited[k] - 1 가 최단거리의 시간이다

 

2. 가장 빠른 시간으로 동생으로 가는 경우

- 경우의 수는 cnt배열이 0인 상태에서 이전 방문 노드의 cnt를 더하면서 계산한다

- 이미 방문한 노드라도 최단소요시간과 같다면 한번 더 방문할 수 있다

 

3. 반례

수빈이와 동생의 위치가 같다면 시간은 0이고 경우는 1이다

💻 코드

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

public class Main{
	static final int MAX=200000;
	static Queue<Integer> queue=new LinkedList<>();
	static int visited[]=new int[MAX+4];
	static int cnt[]=new int[MAX+4];
	
	static void bfs(int here){
		visited[here]=1;
		cnt[here]=1;
		queue.add(here);
		
		while(!queue.isEmpty()){
			int now=queue.poll();
			for(int next: new int[]{now-1,now+1,now*2}){
				if(0<=next && next<=MAX){
					if(visited[next]==0){
						queue.add(next);
						visited[next]=visited[now]+1;
						cnt[next]+=cnt[now];
					}
					else if(visited[next]==visited[now]+1){
						cnt[next]+=cnt[now];
					}
				}
			}
		}
	}
    public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n,k;
		StringTokenizer st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		
		//반례
		if(n==k){
			System.out.println("0");
			System.out.println("1");
			return;
		}
		bfs(n);
		System.out.println(visited[k]-1);
		System.out.println(cnt[k]);
	}
}