[1697] 숨바꼭질

문제

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

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

입력

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

출력

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

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int N, K;
bool discovered[100001];

void bfs(int start){
	queue<pair<int,int>> q;
	discovered[start] = true;
	q.push({start, 0});
	while(!q.empty()){
		pair<int, int> here = q.front();
		q.pop();
		
		
		if(here.first == K){
			cout << here.second;
			return;
		}

		int there;

	
		there = here.first + 1;
		if(0<=there && there<=100000){
			if(!discovered[there]){
				q.push({there, here.second+1});
				discovered[there] = true;
			}
		}

		there = here.first*2;
		if(0<=there && there<=100000){
			if(!discovered[there]){
				q.push({there, here.second+1});
				discovered[there] = true;
			}
		}
	


		there = here.first - 1;
		if(0<=there && there<=100000){
			if(!discovered[there]){
				q.push({there, here.second+1});
				discovered[there] = true;
			}
		}
	}
	
}


int main(void){
	cin >> N >> K;
	memset(discovered, false, sizeof(discovered));

	bfs(N);
	
	return 0;
}

문제 유형을 찾기 위해 몇가지 접근을 해보았다.

1. 완전탐색 => 시간초과

2. 동적 계획법 => 막상 dp를 적용하려 했으나 딱히 겹치는 부분도 없고 메모이제이션을 쓰기에도 애매해서 다른 방법 모색

3. dfs / bfs => 최소값을 구하는 문제이니 dfs보단 bfs가 낫다고 판단 

결론, bfs를 사용하여 문제 풀이

 

아무래도 문제에 맞는 문법을 찾는게 가장 중요한것 같다. 나머지는 문법에 맞는 풀이를 끼워맞추면 되니 말이다...

 

 

*참고*

꿀팁 단축키를 몇가지 발견해서 써놓을려한다!

1. Ctrl + D : 똑같은 단어를 내려가면서 하나씩 선택할 수 있다.

2. Shift + Tap : Tap만큼 뒤로간다.