BOJ 1697 숨바꼭질(C++)

숨바꼭질 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7407	1874	1227	22.952%

문제

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

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

입력

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

출력

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

예제 입력 

5 17

예제 출력 

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번

• 문제를 번역한 사람: author6

링크

• PKU Judge Online
• TJU Online Judge

알고리즘 분류

• BFS

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include<stdio.h> #include<queue> #pragma warning(disable : 4996) static std::queue<int> q; static int TIME[111111]; static int N, K; void hide() {     while (!q.empty())     {         int p = q.front();         q.pop();         if (p == K)             return;         if (p + 1 <= 100000 && TIME[p + 1] == 0)         {             q.push(p + 1);             TIME[p + 1] = TIME[p] + 1;         }         if (p - 1 >= 0 && TIME[p - 1] == 0)         {             q.push(p - 1);             TIME[p - 1] = TIME[p] + 1;         }         if (2 * p <= 100000 && TIME[2 * p] == 0)         {             q.push(2 * p);             TIME[2 * p] = TIME[p] + 1;         }     } } int main() {     scanf("%d %d", &N, &K);     q.push(N);     TIME[N] = 0;     hide();     printf("%d", TIME[K]);     return 0; }

전형적인 BFS문제였다. 

장기, 저글링? 등 기본적인 BFS 문제는 

queue와 방문을 확인할 만한 배열, COST(여기서는 시간)를 저장할 만한 배열 정도가 필요하다. 

(여기서는 방문과 시간을 동일한 배열로 처리하였다. - 메모리를 줄이기 위해)