[백준 스터디 1주차] 12851번 숨바꼭질2 골드5 - 자바(JAVA) / BFS

📑 문제

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

12851번: 숨바꼭질 2

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

 

 

 

 

 

 

✒️ 풀이

 숨바꼭질1(https://eijun.tistory.com/277) 문제에서 같은 초에 이뤄진 선택들은 다음 초에 모두 똑같이 처리해야 한다고 말했다. 깊이를 유지해주는 것이다.

 

 이번 숨바꼭질2 문제는 이 개념을 따로 코드화 시킨 것으로 응용하기 그다지 어렵지 않다.

 ✔️ 이전 문제가 동생을 찾는 순간 바로 탐색을 끝냈다면, 이번 문제는 동생을 찾는 순간 경우의 수를 카운팅 해준다. 

 

 예를 들어 위치 8에 동생이 있고, 2초대에 수빈이가 있는 위치가 5, 6이라고 하자. 이때 수빈이가 아래와 같이 선택해서 이동했다고 해보자.

 ◻️ 위치 5에서 뒤로 이동한다: 위치 4

 ◻️ 위치 6에서 앞으로 이동한다: 위치 7

 

 그리고 3초대에서 아래와 같이 이동했다고 해보자.

 ◻️ 위치 4에서 순간이동한다: 위치 8

 ◻️ 위치 7에서 앞으로 이동한다: 위치 8

 

 이때 숨바꼭질1 문제였다면, 위치4에서 순간이동을 했을 때 동생을 찾고 바로 탐색을 끝냈을 것이다. "3초대"에 동생을 찾았는지만 보면 되기 때문에, 다음 계산은 불필요하기 때문이다. 찾았으면 끝!!!

 이번 문제에서는 동생을 찾은 경우의 수까지 필요하므로, 탐색을 끝내면 안된다. 

 같은 깊이(초)에 있는 모든 경우에 대해 조건을 만족하는지 확인해보고 경우의 수를 카운팅한다.

 이 값이 1보다 크다면 동생을 어떻게든 찾은 경우의 수가 존재한다는 뜻이므로, 그때의 시간과 경우의 수를 출력한 다음 알고리즘을 종료한다.

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_백준_12851_숨바꼭질_골드5 {

	static int N, K, MAX=100000;
	static boolean[] visited;
	static Queue<Integer> queue;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());//수빈이 위치
		K = Integer.parseInt(st.nextToken());//동생 위치
		
		visited = new boolean[MAX+1];
		queue = new LinkedList<Integer>();
		queue.offer(N);
		
		int time = 0;
		while(true) {
			int cnt = bfs();
			if(cnt>0) {
				System.out.println(time);
				System.out.println(cnt);
				break;
			}
			time++;
		}
	}//end of main
	
	private static int bfs() {
		int cnt = 0;
		int size=queue.size();
		for (int i = 0; i < size; i++) {//이전 초에 이동한 모든 경우 탐색
			int cur = queue.poll();
			visited[cur]=true;
			
			if(cur==K) {
				cnt++;//경우의수 카운트
				continue;
			}
			
			if(cur*2 <= MAX && !visited[cur*2]) queue.offer(cur*2);
			if(cur+1 <= MAX && !visited[cur+1]) queue.offer(cur+1);
			if(cur-1 >= 0 && !visited[cur-1]) queue.offer(cur-1);
		}
		return cnt;
	}
}//end of class

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨