[백준 스터디 1주차] 1697번 숨바꼭질 실버1 - 자바(JAVA) / BFS

📑 문제

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

1697번: 숨바꼭질

문제

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

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

 

입력

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

 

출력

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

 

 

 

 

 

 

 

✒️ 풀이

 

💡 가장 빠른 시간을 출력해야 하므로, 이전에 방문한 위치는 다시 볼 필요가 없다. 방문처리 배열이 필요하다.

 

 

💡 한 초에 수빈이는 걸어서 앞으로 이동하거나/ 걸어서 뒤로 이동하거나/ 순간이동을 하거나, 세 가지의 선택을 할 수 있다. 따라서 어떻게 이동하든 이전에 한 선택이 같은 깊이(초)로 처리되어야 하기 때문에, 매 루프마다 큐에 남아있는 이동값을 모두 빼서 처리해줘야한다. 모두 같은 시간대에 이동한 경우이기 때문이다.

 

 예를 들자면 아래와 같다.

 ✔️ 0초에 수빈이(현재위치 5)는 앞(6), 뒤(4), 순간이동(10) 세 개를 모두 했다. 이때 이동위치를 저장한 큐 사이즈는 3이 된다.

6

4

10

 ✔️ 1초에 수빈이는 큐 사이즈 3만큼 이동값을 빼서 처리할 것이다.

 위치6에서 앞(7), 순간이동(12)를 하고, 위치 4에서 뒤(3), 순간이동(8)을 하고, 위치 12에서 앞(13), 뒤(11), 순간이동(24)을 하고나면 큐의 상태는 아래와 같아진다.

7

12

3

8

13

11

24

 ✔️2초에는 큐 사이즈 7만큼 이동값을 빼서 처리하게 될 것이다. 

 이렇게 계속해서 반복한다.

 

 

 

 

 

 

 

 

 

💻 소스코드: 자바(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_백준_1697_숨바꼭질_실버1 {

	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());//동생 위치
		int max = 100000;
		boolean[] visited = new boolean[max+1];
		
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(N);
		
		int time=0;
ex:		while(true) {
			int size=queue.size();
			for (int i = 0; i < size; i++) {//이전 타임에 이동한 경우를 모두 처리한다.
				int cur = queue.poll();
				visited[cur]=true;
				
				if(cur==K) break ex;
				if(cur*2 <= max && !visited[cur*2]) queue.offer(cur*2);
				if(cur-1 >= 0 && !visited[cur-1]) queue.offer(cur-1);
				if(cur+1 <= max && !visited[cur+1]) queue.offer(cur+1);
			}
			time++;
		}
		System.out.println(time);
	}//end of main
}//end of class

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

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