[백준BOJ] 12851번 숨바꼭질2.java

 

백준 저지에서 숨바꼭질2를 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

12851번 숨바꼭질2.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

12851번 숨바꼭질2

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

설명

숨바꼭질 시리즈 문제 중 하나이다. 전과 마찬가지로 bfs를 통해 풀었다. 다음은 숨바꼭질3 풀이 링크이다. 

https://moz1e.tistory.com/485?category=835294 

[백준BOJ]13549번 숨바꼭질3.java

 

가장 빠른 시간뿐만 아니라 가장 빠른 시간으로 찾는 방법이 몇가지인지도 구해야한다. 숨바꼭질3에서는 찾기만 하면 바로 return하여 답을 구했는데 방법까지 구해야 했으므로 가능한 모든 경우를 세기위해서 현재 시간과 같은 경우에도 K에 접근하였다.

 

코드

//12851번 숨바꼭질2.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 숨바꼭질2_12851 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int[] visit;
    static int count;
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		visit = new int[100001];
		Arrays.fill(visit, -1);
		count =0;
		bfs(visit, N, K);
		System.out.println(visit[K]);
		System.out.println(count);
	}
    
    static void bfs(int[] visit,int N, int K) {
    	Queue<Integer> q = new LinkedList<Integer>();
    	visit[N]=0;
    	q.add(N);
    	while(!q.isEmpty()) {
    		int now = q.poll();
    		
    		if(now==K) {
    			count++;
    		}
    		
    		if(2*now<=100000 && (visit[2*now]==-1 || visit[2*now] >= visit[now]+1)) {
    			visit[2*now] = visit[now]+1;
    			q.add(2*now);
    		}
    		if(now+1<=100000 && (visit[now+1]==-1 || visit[now+1] >= visit[now]+1)) {
    			visit[now+1] = visit[now]+1;
    			q.add(now+1);
    		}
    		if(now-1>=0 && (visit[now-1]==-1 || visit[now-1] >= visit[now]+1)) {
    			visit[now-1] = visit[now]+1;
    			q.add(now-1);
    		}
    		
    	}
    }
    
}