[백준] 1697번 숨바꼭질 문제 BFS로 풀어보기
1. 문제
1) 링크
2) 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
3) 입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
4) 출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
문제의 제한에 대해서 더 자세히 알아보기 위해서는 위의 백준 링크로 가보자
2. 풀이
이 문제는 BFS로 풀 수 있는 가장 대표적인 문제이다.
수빈이의 위치가 x일때 각각 x-1, x+1, 2*x 로 갈 수 있고 세 가지 방법 다 1초가 걸리기 때문이다. 또한 가장 빠른 시간을 출력하는 것이기 때문에 DFS보다 BFS가 적합하다.
x-1로 갔다고 생각하면,
x-1의 시간은 x에서의 시간에서 +1을 한 것이고,
check[x-1]은 true (사용되었다는 뜻)로 바꿔주고 queue 에 x-1를 추가해주게 됩니다.
해당 링크를 살펴보면,
if (x>=1){
if (!check[x-1]){
q.add(x-1);
check[x-1]=true;
time[x-1]=time[x]+1;
}
}위와 같이 쓸 수 있다. x-1로 갈 수도 있고 x+1로 갈 수도 있고, 2*x로 갈수도 있으니 위와 같은 코드를 세가지 버전으로 다 적어주어야 한다. 여기서는 BFS이기 때문에 세가지 경우를 모두 다 처리해주고 queue가 empty일때까지 while문을 돌려 처리해주게 된다.
3. 코드
세가지 경우를 모두 처리해준 전체 코드를 살펴보자.
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int start=sc.nextInt();
int MAX=1000000;
int end=sc.nextInt();
Queue <Integer> q= new LinkedList<>();
boolean check[]=new boolean[MAX+1];
int time[]=new int[MAX+1];
check[start]=true;
time[start]=0;
q.add(start);
while(!q.isEmpty()){
int x= q.remove();
if (x>=1){
if (!check[x-1]){
q.add(x-1);
check[x-1]=true;
time[x-1]=time[x]+1;
}
}
if (x+1<=MAX){
if (!check[x+1]){
q.add(x+1);
check[x+1]=true;
time[x+1]=time[x]+1;
}
}
if (2*x<=MAX){
if (!check[2*x]){
q.add(2*x);
check[2*x]=true;
time[2*x]=time[x]+1;
}
}
}
System.out.println(time[end]);
}
}모두 다 유사한 형태로 진행되는 것을 알 수 있다.
다 한뒤에 time[end]를 출력해주면 해당 위치까지 오는데 걸린 최소 시간을 구할 수 있다.
만약 check 배열을 사용하지 않았다면 BFS 알고리즘이 아닐 뿐더러 최소 시간을 구할 수 없었을 것이다.
여기서 어느 장소를 거쳐갔는지까지 history를 모두 다 출력하고 싶다면,
그 문제는 위와 같고, 해당 포스팅은
https://www.programmingstory.com/2024/03/13913-4.html
위에서 했으니 살펴보자.