[C++] 백준 1697번: 숨바꼭질

문제

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

1697번: 숨바꼭질

풀이

X가 3가지 연산을 이용해 K가 되는 최소 연산 횟수를 구하는 문제다.
X에서 x-1, x+1, x*2를 할 수 있으니 3^n의 모든 경우의 수를 싹싹 뒤져서 만드는게 맞는걸까?
아무리 생각해봐도 아닌 것 같아서 검색의 도움을 받았다.

하지만 싹싹 뒤지는게 맞았었다.
수학 공식으로 풀 수 있을거라 생각했는데 내가 검색을 잘 못한건지 못 찾았다.

최단 시간을 구하는거라 BFS를 이용하여 풀었다.


🚩주의할 점

• 큐 사이즈를 for문 조건문에 q.size()로 넣은 점

int qSize = q.size();
for(int i=0; i{    // ... 

q.size()는 for문 안에서 증가된다. 해당 sec에서 추가된 queue만 검토한 후 sec++ 해야 하기때문에 int qSize 변수를 선언해주었다.

• 최댓값을 검사하려고 isValid()라는 함수를 생성했는데 <=, >=라는 연산을 써서.. 틀렸다..........

bool isValid(int num)
{
    if(num > MAX || num < 0)
        return false;
        
    return true;
}

소스

#include <iostream>
#include <queue>
#define MAX 100000
 
std::queue<int> q;
bool visited[MAX + 1];
 
bool isValid(int num)
{
    if(num > MAX || num < 0)
        return false;
        
    return true;
}
 
int BFS(int K)
{
    int sec = 0;
    int data = 0;
    
    while(1)
    {
        int qSize = q.size();
        for(int i=0; i<qSize; ++i)
        {
            data = q.front(); q.pop();
            if(data == K)
            {
                return sec;
            }
            
            if(isValid(data-1) && !visited[data-1])
            {
                visited[data-1] = true;
                q.push(data-1);
            }
        
            if(isValid(data+1) && !visited[data+1])
            {
                visited[data+1] = true;
                q.push(data+1);
            }
        
            if(isValid(data<<1) && !visited[data<<1])
            {
                visited[data<<1] = true;
                q.push(data<<1);
            }
        }
        sec++;
    }
}
 
int main()
{
    
    int N=0, K=0;
    std::cin >> N >> K;
    
    visited[N] = true;
    q.push(N);
    std::cout << BFS(K);
    
    return 0;
}