백준 1697 : 숨바꼭질 c++

코드

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

int main(){
	
	int N, K;
	bool visited[100010];
	int ans = 0;
	cin >> N >> K;
	memset(visited, false, sizeof(visited));
	
	queue<pair<int, int> > q;
	q.push(make_pair(N, 0));
	
	while(!q.empty()){
		int a = q.front().first;
		int cost = q.front().second;
		q.pop();
		
		if(a == K){
			ans = cost;
			break;	
		}
		if(0 <= a-1 && !visited[a-1]){
			visited[a-1] = true;
			q.push(make_pair(a-1, cost+1));
		}
		if(a+1 <= K && !visited[a+1]){
			visited[a+1] = true;
			q.push(make_pair(a+1, cost+1));
		}
		if(a*2 <= K+1 && !visited[a*2]){
			visited[a*2] = true;
			q.push(make_pair(a*2, cost+1));
		}
	}
	cout << ans;
	
	return 0;
}

설명

처음에 dp로 풀어보려했는데 감이 안잡혀서 구글링을 해보니 bfs를 이용하는 문제였다.

1. 큐에다가 현재위치와 cost를 넣는다.

2. 갈수있는 곳인 현재위치-1, 현재위치+1, 현재위치*2 인 곳이 범위내인지 확인한다.

3. 간적이 없다면 가봤다고 체크하고, 큐에 그곳의 위치와 cost+1를 넣는다.

4. pop된 큐에서 원하는 위치가 나오면 cost를 출력하고 종료한다.

 

여기서 중요한점은 범위가 a-1 >=0 이고, a+1 <= K 이고

a*2 <= K+1 이라는 점입니다. K+1로갔다가 -1로 가는 경우가 있기 때문이죠