[C++] 백준 1697 : 숨바꼭질

백준 1697 : 숨바꼭질

 

문제 링크

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

문제 내용

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

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

 

 

Idea

1초 후에 수빈이가 이동할 수 있는 경우는 3가지가 있다.

• X - 1
• X + 1
• X * 2

현재 위치가 x라면 3가지 방향으로 이동하는 것으로 큐에 삽입하여 구현하는 것은 쉽다.

하지만, 별다른 제제 없이 진행한다면 요소가 지수적(3^n)으로 늘어나 결국 메모리 초과를 유도한다.

(그게 바로 나다...)

 

따라서 큐에 위치를 삽입할때는 아래와 같은 조건들이 만족해야 한다.

• 방문하지 않은 위치
• 100,000보다 작거나 같아야 한다.
• 0보다 크거나 같아야 한다.

 

+) 아래 코드에서

queue의 첫 번째 요소 : 시간

queue의 두 번째 요소 : 위치

 

 

Code

#include <stdio.h>
#include <queue>
#define SIZE 100000
using namespace std;
 
bool visit[SIZE + 1];
 
int main() {
    int N, K;
    scanf("%d %d", &N, &K);
 
    queue<pair<int, int>> q;
    q.push(make_pair(0, N));
    visit[N] = true;
 
    int result = 0;
    while (1) {
        int cnt = q.front().first;
        int place = q.front().second;
 
        //위치를 찾았다면 break
        if (place == K) {
            result = cnt;
            break;
        }
 
        //세가지의 경우를 조건에 맞춰 push
        if (place - 1 >= 0 && !visit[place - 1]) {
            q.push(make_pair(cnt + 1, place - 1));
            visit[place - 1] = true;
        }
        if (place + 1 <= SIZE && !visit[place + 1]) {
            q.push(make_pair(cnt + 1, place + 1));
            visit[place + 1] = true;
        }
        if (place * 2 <= SIZE && !visit[place * 2]) {
            q.push(make_pair(cnt + 1, place * 2));
            visit[place * 2] = true;
        }
 
        //사용한 큐는 pop
        q.pop();
    }
    printf("%d\n", result);
    return 0;
}