[백준 1697] 숨바꼭질

0. 제목

• 백준 1697 숨바꼭질
• BOJ 1697 숨바꼭질
• C++ 1697 숨바꼭질

---

1. 문제

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

---

2. 풀이

• 완전탐색을 푸는데에 5가지 방법이 있다.
  • brute force(N중 for문)
  • 순열
  • BFS(최소를 구하는 문제)
  • 비트마스크
  • 백트래킹
• 이 문제는 BFS를 사용하여 푼다.
• 현재위치와 현재까지 걸린 시간을 큐에 넣고 조건을 확인해가며 push, pop을 반복한다.
• 그렇게 반복문을 돌다가 현재위치가 동생이 있는 위치와 같아지게 되면 bfs함수는 현재까지 걸린시간을 반환한다.

---

3. 코드

#include <iostream>
#include <queue>
using namespace std;
 
const int MAX = 100001;
bool visited[MAX];
 
int bfs(int N, int K){
    queue<pair<int, int>> q;
    q.push(make_pair(N, 0));
    visited[N] = true;
    
    while(!q.empty()){
        int loc = q.front().first;
        int sec = q.front().second;
        q.pop();
        
        if (loc == K) {
            return sec;
        }
        
        if(loc + 1 < MAX && !visited[loc + 1]){
            visited[loc + 1] = true;
            q.push(make_pair(loc + 1, sec + 1));
        }
        if(loc - 1 >= 0 && !visited[loc - 1]){
            visited[loc - 1] = true;
            q.push(make_pair(loc - 1, sec + 1));
        }
        if(loc * 2 < MAX && !visited[loc * 2]){
            visited[loc * 2] = true;
            q.push(make_pair(loc * 2, sec + 1));
        }
    }
    return 100000;
}
 
int main(int argc, const char * argv[]) {
    int N, K;
    cin >> N >> K;
    
    cout << bfs(N, K) << '\n';
    
    
    return 0;
}