백준 17071 - 숨바꼭질 5(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

생각을 해야되는 BFS 문제였습니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

#define P pair<int,int>
#define PP pair<P, int>
#define F first
#define S second
#define Max 500001
#define INF 987654321

using namespace std;

int N, K, mini = INF;
int check[2][Max]; // 0->짝수 , 1->홀수
int Find[Max];

void go_first(int start){
	for(int i = 0; i < Max; i++){
		Find[i] = -1;
	}
	int Add = 1;
	while(1){
		if(start > Max - 1) break;
		Find[start] = Add-1;
		start += Add++;
	}
}

void bfs(){
	queue<P> q;
	q.push({0,N});
	check[0][N] = 1;
	while(!q.empty()){
		int cnt = q.front().F;
		int x = q.front().S;
		// cout << x << " " << cnt << "\n";
		q.pop();
		if(x > Max - 1) break;
		if(Find[x] != -1 && cnt % 2 == Find[x] % 2 && cnt <= Find[x]){
			mini = min(mini, Find[x]);
		}
		int x1 = x + 1;
		int x2 = x - 1;
		int x3 = x * 2;
		if(x1 >= 0 && x1 < Max){
			if(check[(cnt+1) % 2][x1] == 0){
				check[(cnt+1) % 2][x1] = 1;
				q.push({cnt+1, x1});
			} 
		}
		if(x2 >= 0 && x2 < Max){
			if(check[(cnt+1) % 2][x2] == 0){
				check[(cnt+1) % 2][x2] = 1;
				q.push({cnt+1, x2});
			} 
		}
		if(x3 >= 0 && x3 < Max){
			if(check[(cnt+1) % 2][x3] == 0){
				check[(cnt+1) % 2][x3] = 1;
				q.push({cnt+1, x3});
			} 
		}
	}
}

void solve() {
	go_first(K);
	bfs();
	if(mini == INF) cout << "-1";
	else cout << mini;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요