[백준 1697] 숨바꼭질

🔗알고리즘 문제

아직 그래프 탐색 문제의 응용은 조금 약하구나 라는 생각이 든 문제, 그래프 탐색은 더욱 연습이 필요할 것 같다..

문제 분석

이 문제는 수빈이가 동생을 찾는 가장 빠른 경우를 찾아내는 문제이다.

이때 수빈이가 1초가 지날동안 할 수 있는 행동은 다음과 같이 3가지가 존재한다.

1. 현재 위치에서 한칸 앞으로 가기
2. 현재 위치에서 한칸 뒤로 가기
3. 현재 위치에 2배 위치로 순간이동하기 

예를 들어 수빈이가 처음 있는 칸이 5 동생의 위치가 17인 상황일 때, 수빈이는 다음과 같이 행동하여 동생을 찾아낼 수 있다.

시작 : 5

3번 행동 - 10
2번 행동 - 9
3번 행동 - 18
2번 행동 - 17

경과 시간 : 4 ( 초 )

발상 & 알고리즘 설계

문제의 조건을 보면 값의 입력이 최대 100,000개가 들어오게 된다. DFS를 사용하게 되면 처음부터 100,000개의 데이터를 모두 검사해야 되기에 비효율적이다라고 판단하였다. BFS를 사용하여 문제를 해결하기로 마음먹었다.

1. 현재 수빈이가 있는 칸에서 갈 수 있는 칸 ( 3가지 행동 ) 을 탐색한다.
2. 이 때 이미 탐색한 지역과 갈 수 없는 칸 ( 0미만 target초과 )는 스킵한다.
3. 탐색한 칸을 큐에 넣어준다.
4. 만약 탐색한 칸에 동생이 있다면 현재까지 경과 된 초를 출력한다.

이런 식의 구조로 알고리즘을 짜기로 결정하였다.

while(q.empty() == false){
    pair<int, int> cur = q.front();
    q.pop();

    for(int i = 0; i < 3; i++){
        pair<int, int> next = { dest(cur.first, i), cur.second + 1 };

        if(next.first == k){
            cout << next.second;
            return 0;
        }

        if(next.first < 0 || next.first > k + 1)
            continue;
        if(check[next.first - 1] == true)
            continue;

        check[next.first - 1] = true;
        q.push(next);
    }
 }

나름 잘 해결했다고 생각했지만 이 코드에는 내가 생각치 못했던 문제점이 있었다.

나는 무의식적으로 당연히 k가 n보다 클 것이라고 생각하고 있었다. 하지만 k가 n보다 작은 상황도 존재할 수 있다는 걸 놓치고 있었다.

만약 k가 n보다 작은 상황이라면

if(next.first < 0 || next.first > k + 1)
    continue;

해당 조건에 걸려 재대로 된 탐색이 불가능 하였다.

갈수 없는 칸을 하나하나 검사해주는 방식으로 알고리즘을 수정하여 문제를 해결하였다.

코드

#include<iostream>
#include<queue>

using namespace std;

bool check[100001] = {};

int main(){
    int n;
    int k;

    cin >> n >> k;

    queue<pair<int, int>> q;
    q.push({ n, 0 });

    while(q.empty() == false){
        pair<int, int> node = q.front();
        q.pop();

        if(node.first == k){
            cout << node.second;
            break;
        }

        if(node.first + 1 <= k && check[node.first + 1] == false && n < k){
            check[node.first + 1] = true;
            q.push({ node.first + 1, node.second + 1 });
        }

        if(node.first - 1 >= 0 && check[node.first - 1] == false){
            check[node.first - 1] = true;
            q.push({ node.first - 1, node.second + 1 });
        }

        if(node.first * 2 <= k + 1 && check[node.first * 2] == false && n < k){
            check[node.first * 2] = true;
            q.push({ node.first * 2, node.second + 1 });
        }
    }
}