[백준 - 1697] 숨바꼭질 - C++, Python

분류: bfs, 1차원 BFS, 재귀 /

 

문제

문제 링크

문제 설명

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

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

입력

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

출력

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

 

풀이

- C++ (BFS)

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

int N, K;
int dist[100001];
queue<int> Q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> K;
    if(N == K) {
        cout << 0;
        return 0;
    }
    
    Q.push(N);
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        for(int nx: { x-1, x+1, 2*x }) {
            if(nx < 0 || nx > 100000) continue;
            if(nx == N || dist[nx] > 0) continue;
            if(nx == K) {
                cout << dist[x] + 1;
                return 0;
            }
            dist[nx] = dist[x] + 1;
            Q.push(nx);
        }
    }
    throw;
}

위처럼 연산을 처리 할 때 `range-based loop`를 활용할 수 있다.

# BFS

N에서 K에 도달할 때까지 bfs를 돌며 N으로 부터 거리를 `dist`에 기록한다.

주의할 점은 while문은 `N == K`를 바로 걸러내지 못한다. 따라서 bfs전에 `N == K`를 확인해 준다.

만약 확인해 주지 않으면 `dist`가 모두 채워지고 이후 모든 `nx`가 범위를 벗어나 버려진다. 큐에는 더이상 push되지 않아 큐가 비고 while문이 종료된 후 `main` 마지막에 도달해 `throw`가 던져진다.

아래와 같이 처리할 수 도 있다.

while(dist[K] == 0) { // k가 계산되면 종료
    int x = Q.front(); Q.pop();
    for(int nx: { x-1, x+1, 2*x }) {
        if(nx < 0 || nx > 100000) continue;
        if(nx == N || dist[nx] > 0) continue;
        dist[nx] = dist[x] + 1;
        Q.push(nx);
    }
}
cout << dist[K];

# dist의 범위

문제에서 `0 ≤ N, K ≤ 100000`이고 세개의 연산 중 뒤로 가는 연산(`X - 1 연산`)이 있다. 

우선 음수로 내려가면 곱하기는 K와 더 멀어지고 더하기로 만 K에 가까워 질 수 있으므로 빼기로 음수로 내려가는 순간 절대 최소 연산횟수가 될 수 없다. 따라서 `dist`의 하한이 0임은 쉽게 알 수 있다.

문제는 상한인데 `N = 50001, K = 100000`일때, `2 * X 연산`으로 K를 넘어간 뒤 `X - 1 연산`으로 내려오는 상황도 가능하기 때문에 상한을 200000으로 잡아야한다고 생각할 수 있다. (`2 * X 연산` -> `X - 1 연산` -> `X - 1 연산`)

하지만 조금 생각해보면 상한은 100000으로 충분하다. 이를 증명해보면 다음과 같다.

증명은 `2 * X 연산` 결과가 K를 넘어 갈 때,

(`2 * X 연산` -> `X - 1 연산` 여러번) 보다 (`X - 1 연산` 여러번 -> `2 * X 연산`)이 더 빠르다는 것을 보이면 된다.

아래 증명은 K가 짝수 일때는 항상 위 명제가 참이고 홀수일때는 r > 1일때 참임을 보인다. K의 최댓값이 100000이고 가장 큰 홀수 값은 99999이다. 홀수 일때 r = 1일 때만 거짓이므로 dist의 상한은 100000으로 충분하다.

$$\text{when}\quad n< K<2n\quad\text{always}\quad t_1< t_2\\[0.5em]t_1:(X-1\text{ several times) after }(X\times2)\\[0.3em]t_2:(X\times2)\text{ after }(X-1\text{ several times})\\[0.8em]\begin{align*}\text{prof.}\quad&\text{case 1:}&&K=2p,\space n=p+r,\space 0< r< n\\[0.5em]&\text{method 1:}&&K=(n-r)\times2\\[0.3em]&&&t_1=r+1\\[0.5em]&\text{method 2:}&&K=(2\times n)-2r\\[0.3em]&&&t_2=1+2r\\[0.3em]&&&\therefore\space t_1< t_2\\[0.5em]&\text{case 2:}&&K=2p+1,\space n=p+r,\space 0< r< n\\[0.5em]&\text{method 1:}&&K=(n-r)\times2+1\\[0.3em]&&&t_1=r+1+1\\[0.5em]&\text{method 2:}&&K=(2\times n)-2r+1\\[0.3em]&&&t_2=2-2r\\[0.5em]&&&\therefore\space t_1< t_2(r>1)\end{align*}$$

 

- C++ (재귀)

#include <iostream>
using namespace std;

int f(int n, int k) {
    if(n >= k) return n - k;
    if(k == 1) return 1;
    if(k % 2) return min(f(n, k+1), f(n, k-1)) + 1;
    return min(k-n, f(n, k/2) + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K; cin >> N >> K;
    cout << f(N, K);
}

이 문제를 처음 보고 백준 16953번 A -> B 문제가 생각났다.

우선 `n >= k`이면 n - k번의 `X - 1 연산`으로 도달할 수 있다.

`n < k && k == 1`이면 `n == 0 && k == 1`인 상황 뿐이다. 이때는 1번의 `X + 1 연산`으로 도달할 수 있다.

그 외에 `n < k`이면 항상 다른 연산보다 `X * 2 연산`이 빠르다.

따라서 `k`가 홀수면 `X * 2 연산`으로 k에 가장 가까운 짝수로 간 뒤 `X + 1 연산` 혹은 `X - 1 연산`으로 도달하는 방법이 빠르다.

`k`가 짝수이면 `X + 1 연산`과 `X * 2`연산 중 빠른 방법으로 도달한다.

 

- Python (BFS 순차 실행)

import sys
n, k = map(int, sys.stdin.readline().split())

def bfs(n,k):
    visited = set()
    Q = [n]
    sec = 0
    while True:
        nextQ = []
        for i in Q:
            if i in visited: continue
            if i < 0 or i > 100000 : continue
            visited.add(i)
            if i == k:
                return sec
            elif i > k:
                nextQ.append(i - 1)
            else:
                nextQ.extend([i - 1, i + 1, 2 * i])
        sec += 1
        Q = nextQ
        
print(bfs(n,k))

파이썬으로는 다르게 풀어봤다. 같은 generation씩만 돌리는 BFS 순차 실행으로 구현했다.