[백준] 1697번: 숨바꼭질 풀이 및 해설(C++)

 

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

1697번: 숨바꼭질

 

C++로 작성한 백준 문제 1697번 숨바꼭질에 대한 문제 풀이다.

실버 1 문제로 ~이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

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

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

입력

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

출력

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

 

---

문제 파악하기

1. 처음에는 그냥 계속 2배 하다가 제일 가까워졌을 때 1씩 이동하면 되는 거 아닌가? 생각했다. 하지만 예시에 나온 대로 후퇴한 후 순간이동 하거나 전진한 후 순간이동 하는 게 더 빠를 수 있다.
2. 수빈의 위치가 동생의 위치보다 크다고 가정해보자, 수빈과 동생의 위치는 음수가 아니므로,  계속 1씩 후퇴해서 가면 된다. 그냥 수빈과 동생의 거리차이만큼의 턴이 걸리는 것이다.
3. 수빈의 위치가 동생의 위치보다 작다고 가정해보자. 순간이동을 한다면 최대 몇까지 가는 경우가 있을까? 동생의 위치를 K라고 하자. 수빈의 위치가 K-1이라면 바로 1칸 전진으로 골인할 수 있으므로 굳이 2배 순간이동을 할 필요가 없다. 즉, 2배로 순간이동 하는 경우는 최대 K-2에서이다. 수빈의 위치가 존재할 수 있는 최댓값 K-2에서 순간이동 한 2K -4나 동생의 위치 K 중 큰 수이다.
4. 반대로, 최소 몇까지 가는 경우가 있을까? 수빈의 위치가 N이라고 하자. 그러면 수빈은 N/2 이하로는 후퇴할 일이 없다. 어차피 2배 순간이동 노린다고 해도 제자리이기 때문이다. 따라서 수빈의 위치가 존재할 수 있는 최솟값은 N/2(반올림해야 함)이다. 
5. 동적계획법은 배열의 값들이 후진 때문에 순서대로 들어갈 수 없으므로 적절하지 않다.
6. DFS 역시 값이 순서대로 들어가지 않아 적절하지 않다.
7. BFS를 써야 한다.

 

 

 

 

 

---

 

코드 및 설명

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
queue<int> q;
int arr[200002];
int K,big,small,ans=0;

void bfs(int pos){
    q.push(pos);
    while(!q.empty()){
        pos=q.front();
        q.pop();
        if(2*pos<=big && arr[2*pos]==0 && pos != 0){
            q.push(2*pos);
            arr[2*pos]=arr[pos]+1;
        }
        if(pos-1>=small && arr[pos-1]==0){
            q.push(pos-1);
            arr[pos-1]=arr[pos]+1;
        }
        if(pos+1<=big &&arr[pos+1]==0){
            q.push(pos+1);
            arr[pos+1]=arr[pos]+1;
        }
        if(pos==K){
            cout<<arr[pos];
            break;
        }
    }

}



int main(){
    fastio;
    int N;
    cin>>N>>K;
    if(N>=K){
        cout<<N-K;
        return 0;
    }
    big = max(2*K-4,K);
    small = min((N-1)/2 + 1,N); 
    bfs(N);
    return 0; 
}

 

• 처음에 배열 인덱스로 가능한 최대와 최소 숫자, big과 small을 미리 잡아놓아야 한다. 이 부분은 문제 풀면서 빠르게 파악했다.
• BFS로 문제를 풀어야 하는데 재귀호출을 이용했다가 에러가 계속 났다.
• BFS는 큐를 이용하고 DFS와 달리 함수 안에서 함수를 호출하지 않고, while문을 쓴다.

 

---

 

헤매었던 부분

• 문제조건에 100000이 최대의 경우라고 진짜 그 언저리로 만들었다가 OutofBounds 에러가 발생하였다. 문제 내에서 2배 이동도 있으므로 그것보다 2배 더 크게 만들어 주어야 했다.
• 시작 위치가 0일 때, 0에서 0으로 2배 이동 제자리 뛰기 하는 에지케이스가 있어서 그 부분을 한번 틀리고 수정하였다. 

 

 

 

 

 

 

---

 

마무리

오랜만에 푼 문제였다. DFS 문제는 많이 풀었는데 BFS 문제는 많이 안 풀어서인지 시간이 오래 걸렸다. BFS에 대해 맞으면서 배웠다.