[알고리즘 풀이 분석] BOJ 13549 숨바꼭질 3

오늘 풀어본 문제는 BOJ 13549 숨바꼭질 3 이다. 골드 5 단계 문제이고 특별할 것 없는 그래프 탐색 문제인 것 같지만 주의할 점이 있었다!

BOJ 13549 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입출력

[입력]
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

[출력]
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

나의 풀이

처음엔 재귀적으로 코드를 작성하였다. 순간 이동에는 초가 증가하지 않으므로 순간 이동부터 순서대로 재귀적으로 함수를 호출하였지만 어쩐지 계속 시간 초과가 발생했다.

아니 논리적으로 틀린 부분이 없는데 왜 이러는거지?? 도대체??

범위도 0~100,000 으로 큰편도 아닌데 왜 그런가 했지만 문제와 함께 제공된 예제 입출력을 보면 수빈이와 동생의 위치가 각각 5, 17 일 때 수빈이는 5->10->9->18->17 과 같이 이동하여 2초만에 동생을 찾을 수 있다.

하지만 재귀적으로 호출한다면 수빈이는 5,10,20,40,,,, 과 같이 저어어어 멀리까지 갔다가 다시 돌아와 10 -> 9 와 같이 이동해야 하는 식이었다. 순간이동 재귀 호출에서 계속 시간 초과가 발생했고 그것이 백준 제출 시점도 아니고 CLion 에서 발생했기 때문에 사실 100% 이해는 안되지만,,

결론적으로 현재 수빈이가 위치한 시점에서 순간이동 하는경우, 한 칸 뒤로 가는 경우, 한 칸 앞으로 가는 경우를 동시에 (완벽히 동시에는 아니지만 아주 가까운 시점 에서) 탐색 해야 한다고 깨달았다.

결국 <queue> 를 사용해 해결하였고 중복 방문을 막기 위해 모든 방문 시점마다 배열 visited 에 체크하였다.

또한 가장 빠른 시점을 찾는 것이기 때문에 "동생의 위치 K 에 첫 도착 = 가장 빠른 시점" 임을 생각해 바로 결과를 반환하고 탐색을 중단하였다.

이를 위해선 탐색의 순서를 순간 이동 > 걷기 와 같이 설정 해 주어야 한다.

다른 분들의 풀이를 찾아보니 우선순위 큐를 사용하신 분도 계셨다. 초가 빠른 것을 먼저 탐색해야 하므로 우선순위 큐를 활용했는데 더 타이트한 조건의 탐색이 필요할 때에는 꼭 필요한 좋은 방법이라고 생각했다!!

• 큐가 사용되는 문제이기 때문에 swift 로도 풀어보았다!

코드

cpp

#include <iostream>
#include <vector>
#include <queue>

// boj 13549 숨바꼭질 3, 골드 5, bfs
using namespace std;

int bfs(int N, int K){
    if(N==K) return 0;

    queue<pair<int, int>> q;
    q.push(make_pair(N, 0));

    vector<bool> visited(100001, false);
    visited[N] = true;

    while (!q.empty()){
        int curr = q.front().first;
        int sec = q.front().second;

        if (curr == K){
            return sec;
        }
        q.pop();

        if (curr*2 <= 100000 && !visited[curr*2]){
            visited[curr*2] = true;
            q.push(make_pair(2*curr, sec));
        }

        if (curr-1 >= 0 && !visited[curr-1]){
            visited[curr-1] = true;
            q.push(make_pair(curr-1, sec+1));
        }

        if (curr+1 <= 100000 && !visited[curr+1]){
            visited[curr+1] = true;
            q.push(make_pair(curr+1, sec+1));
        }
    }
}

int main() {
    int N,K;
    cin>>N>>K;

    cout<<bfs(N, K);

    return 0;
}

swift

import Foundation

struct Queue<T> {
    private var queue : [T?] = []
    private var head : Int = 0
    
    public var count : Int {
        return queue.count
    }
    
    public var isEmpty : Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element : T){
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        guard head <= queue.count, let element = queue[head] else { return nil }
        
        queue[head] = nil
        head += 1
        
        if head>50 {
            queue.removeFirst(head)
            head = 0
        }
        
        return element
    }
}

func bfs(_ N : Int, _ K :Int) -> Int {
    var dp = [Int](repeating: -1, count: 100001)
    dp[N] = 0
    
    var q = Queue<Int>()
    q.enqueue(N)
    
    
    while !q.isEmpty {
        let curr = q.dequeue()!
        if curr == K {
            return dp[curr]
        }
        
        if curr*2 <= 100000 && dp[curr*2] == -1 {
            dp[curr*2] = dp[curr]
            q.enqueue(curr*2)
        }
        
        if curr-1>=0 && dp[curr-1] == -1 {
            dp[curr-1] = dp[curr]+1
            q.enqueue(curr-1)
        }
        
        if curr+1<=100000 && dp[curr+1] == -1 {
            dp[curr+1] = dp[curr]+1
            q.enqueue(curr+1)
        }
    }
    
    return dp[K]
}

let input = readLine()!.split(separator: " ")
let N = Int(input[0])!
let K = Int(input[1])!

print(bfs(N, K))