BOJ 1697 - 숨바꼭질 / C++

문제 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

문제 풀이

요약하면, 현재 위치 n에서 k까지 갈 때 x+1, x-1, 2*x 중 한 가지 과정을 거쳐서 갈 수 있으며 최소 시간(카운트)을 구하면 되는 문제이다. 잠시 DFS와 BFS의 개념을 살펴보면

 

DFS는 아래의 그림처럼 현재 branch를 최대한 깊이 탐색한 후 다음 branch를 탐색하는 방식이며

BFS는 아래의 그림처럼 인접 노드를 모두 탐색한 후 방문하지 않은 다른 노드들에 대해서도 같은 방식으로 탐색하는 방식이다.

만약 이 문제를 DFS로 풀게 된다면 x+1 노드, x+1 노드, x+1 노드, ... 이런 식으로 10만까지 탐색할 것이다. 따라서, 해당 문제는 BFS로 탐색하여 푸는 것이 적절하다.

 

 

소스 코드

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 100001;
bool visited[MAX] = { false, };
int ans[MAX] = { 0, };
queue<int> q;
int n, k;

bool isPossible(int val){
    if(val >= 0 && val < MAX) return true;
    else return false;
}

void BFS(int st){
    q.push(st);
    visited[st] = true;
    ans[st] = 0;

    while (!q.empty()){
        int cur = q.front();
        if(cur == k) break;
        q.pop();

        if(isPossible(cur + 1) && !visited[cur + 1]){
            visited[cur + 1] = true;
            q.push(cur + 1);
            ans[cur + 1] = ans[cur] + 1;
        }
        if(isPossible(cur - 1) && !visited[cur - 1]){
            visited[cur - 1] = true;
            q.push(cur - 1);
            ans[cur - 1] = ans[cur] + 1;
        }
        if(isPossible(cur * 2) && !visited[cur * 2]){
            visited[cur * 2] = true;
            q.push(cur * 2);
            ans[cur * 2] = ans[cur] + 1;
        }
    }
}

int main(){
    cin >> n >> k;
    BFS(n);

    cout << ans[k];
}