BOJ 1697번 : 숨바꼭질

그냥 문제를 읽으면 수학이나 규칙을 찾는것 같지만, 그래프탐색을 탐색해서, 계층구조를 탐색하고, 몇번째 계층에 k가 있는지 찾아내는 문제이다.

그러므로 BFS(너비우선탐색)을 사용하는 문제이다.

 

<Solution>

예시로 문제를 설명해보자.

입력 : 8 20

위와 같은 경우에는, 8 - 9 - 10 - 20 이므로, 3번만에 목적지에 도착할 수 있다.

이처럼 시작값 부터 모든 수를 탐색 해야 한다. 

또한, 몇번만에 가는지를 알아야 한다.

위의 모든 조건을 한번에 해결할 수 있는 방법은 BFS 이다.

아래 그래프를 보자.

이제 계층구조가 한눈에 보인다. 8을 0층으로 새각했을때,  20은 3층에 있다. 즉, 최단거리가 3이라고 생각 할 수 있다.

이미 방문 되어있는 값은 더욱 적은 횟수로 도착할 수 있다는 것이므로, 재방문 하지 않아도 된다.

이것을 구현하기 위해서는 각 value 의 계층을 저장하고, 방문한 value 인지 확인 하는 배열 또는 벡터 한개,

각 value와 계층을 Queue 처리 하기 위한 queue가 각각 필요할 것이다.

 

n과 k가 같은 경우도 꼭 생각해주자!!!

또한, out of Index 때문에 생기는 런타임 에러를 피하기 위해 배열의 길이또한 신경 써주자!!

 

<소스코드>

#include<iostream>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
queue<int>q_1; // value
queue<int>q_2; // count
vector<int>v;  //history
 
int bfs(int n, int k) {
 
    q_1.push(n); // start value 넣어줌
    q_2.push(0); //start count 넣어줌
    while (!q_1.empty()) {
        int temp_v = q_1.front();
        int temp_c = q_2.front();
        q_1.pop();
        q_2.pop();
        if (temp_v == k) { // 판별 1
            return v[temp_v];
            break;
        }
        if ((temp_v - 1)<v.size() && temp_v >=0 && !v[temp_v - 1]) {
            v[temp_v - 1] = temp_c + 1;
            q_1.push(temp_v - 1);
            q_2.push(temp_c + 1);
        }
        if ((temp_v + 1)<v.size() && temp_v >= 0 && !v[temp_v + 1]) {
            v[temp_v + 1] = temp_c + 1;
            q_1.push(temp_v + 1);
            q_2.push(temp_c + 1);
        }
        if ((temp_v * 2)<v.size() && temp_v >= 0 && !v[temp_v * 2]) {
            v[temp_v * 2] = temp_c + 1;
            q_1.push(temp_v * 2);
            q_2.push(temp_c + 1);
        }
        if (v[k]) { //판별 2
            return v[k];
            break;
        }
    }
}
 
int main() {
    int n, k;
    cin >> n >> k;
    v.assign(100001, 0);
    v[n] = 0;
    cout << bfs(n, k) << endl;
    return 0;
}
 

 

<문제>

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

1697번: 숨바꼭질