[백준] 13549번 숨바꼭질3 문제 (BFS의 변형) 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/13549

2) 문제

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

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

3) 입력

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

4) 출력

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

더 자세한 문제의 조건을 찾기 위해서는 위의 백준 링크로 들어가서 확인해보자.

2. 풀이

이 문제는

https://www.programmingstory.com/2024/03/1697-bfs.html

위의 숨바꼭질 문제와 유사하나, 이번 문제에서는 X+1이나 X-1로 이동할 때는 1초가 걸리는 반면, 2*X로 이동할 때는 시간이 0초가 걸린다는 것이 다른 점이다. 만약 모두 다 1초가 걸렸다면 위의 포스팅에서처럼 단순 BFS를 사용하여 문제를 해결할 수 있다.

하지만 이 문제는 걸리는 시간이 가능한 경우마다 다르기 때문에 조금 다른 방식으로 풀어보려고 한다.

이 문제는 0초가 걸리는 경우와 1초가 걸리는 경우를 다르게 처리해주어야 하기 때문에 덱 (deque) 이라는 자료구조를 사용해보려고 한다.

Stack (뒤쪽으로 넣고, 앞쪽에서 하나씩 빼는 구조: Last In First Out), Queue( 앞으로 넣고, 앞쪽에서 하나씩 빼는 구조: First In First Out)과는 달리, 덱 자료구조는 앞, 뒤로 자유롭게 추가하고 뺄 수 있다는 장점이 있다.

addFirst()라는 메서드를 사용하면 자료구조의 앞쪽으로 추가하는 것이고, add()를 하면 deque의 마지막 요소에 추가하는 것이라고 볼 수 있다.

따라서 만약 0초가 걸리는 2*X로 이동할 경우에는 해당 요소를 deque의 앞쪽에 추가하고, 다른 1초가 걸리는 것들의 경우에는 해당 요소를 deque의 뒤쪽에 추가하는 식으로 구성을 한다면 BFS를 변형하여 사용할 수 있다.

deque의 여러가지 메서드와 기능들을 아래의 포스팅에서 다루었으니 만약 처음 접하는 사람들은 먼저 해당 포스팅을 확인해보자.

https://www.programmingstory.com/2024/03/deque-deque.html

deque은 ArrayDeque이라는 자료구조를 사용하고, 해당 부분을 코드로 구현한 것은 다음과 같다. 이 문제에서 check 배열은 해당 위치가 전에 방문되었는지를 확인하는 boolean 배열이고, time 배열은 해당 위치까지 도달하는데 걸리는 시간을 적어두는 배열이다.

 ArrayDeque<Integer> d = new ArrayDeque<Integer>();
 d.add(start);
  while(!d.isEmpty()){
           int x=d.poll();
           int arr[]=new int []{2*x, x+1, x-1};
           for(int i=0; i<3; i++){
               if (arr[i]>=0 &&arr[i]<=MAX){
                   if (check[arr[i]]==false){
                       check[arr[i]]=true;
                       if (i==0){
                           d.addFirst(arr[i]);
                           time[arr[i]]=time[x];
                       }
                       else{
                           d.addLast(arr[i]);
                           time[arr[i]]=time[x]+1;
                       }
                   }
               }
           }
       } d.add(start);

처음에 start 로 입력받는 위치만 deque에 넣고 시작을 한 뒤에 각각 2*x, x+1, x-1의 세 가지 경우를 for문으로 돌면서 처리를 해주는 것이다.

첫 번째 경우 즉 2*x인 경우는 deque의 앞부분에 넣어주기 때문에 addFirst를 사용하고 time 또한 0초이기 때문에 현재 위치에서의 time을 그대로 적용시켜준다.

반면 다른 경우는 deque의 끝부분에 넣어주기 때문에 addLast를 사용하고 time 또한 1초 증가한 것으로 처리를 해준다.

이처럼 서로 여러 가지 경우가 있는데 걸리는 시간이 다르다든지 각각의 가중치가 다를 경우 deque이라는 유용한 자료구조를 사용하여 편리하게 구현할 수 있다.

3. 코드

위의 내용을 모두 종합적으로 판단하여 구현한 코드는 다음과 같다.

import java.util.*;

public class Main{
    public static final int MAX = 1000000;
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int start=sc.nextInt();
        int end=sc.nextInt();
        boolean check[]=new boolean[MAX+1];
        int time[]=new int[MAX+1];
         ArrayDeque<Integer> d = new ArrayDeque<Integer>();
        d.add(start);
        time[start]=0;
        check[start]=true;
       while(!d.isEmpty()){
           int x=d.poll();
           int arr[]=new int []{2*x, x+1, x-1};
           for(int i=0; i<3; i++){
               if (arr[i]>=0 &&arr[i]<=MAX){
                   if (check[arr[i]]==false){
                       check[arr[i]]=true;
                       if (i==0){
                           d.addFirst(arr[i]);
                           time[arr[i]]=time[x];
                       }
                       else{
                           d.addLast(arr[i]);
                           time[arr[i]]=time[x]+1;
                       }
                   }
               }
           }
       }
        System.out.println(time[end]);
    }
}

Programming Story