[BOJ] 백준 17071번 : 숨바꼭질 5 C++ : 아주정은

숨바꼭질 지긋지긋.....

​음 이문제는 4일?정도 생각을 해본것같다.

이문제에 대한 풀이가 많이 않아서 고민을 많이 해야했던것같다.

일단 풀이 방법의 요점은 언니가 짝수초에 방문한 위치는 짝수초에 또 방문할수있다는것이다.

홀수초도 마찬가지이다. 언니가 16이라는 위치에 짝수초에 방문했다면, 다음 +1, -1을 통해서 다음짝수초에도 방문 할 수 있게된다.

어떤풀이는 언니가 방문한 모든 위치를 배열에 저장하는 방식을 하셨다. 그 방법을 써볼려고 하니깐 음...그럼 언니의 위치가 0보다 작아지거나 500000보다 높아져야 끝이나기 때문에 포기하고 다시 내 생각으로 돌아왔다.

먼저, 나는 시간에 따라 동생의 위치를 파악한다.

그리고 현재 큐에는 현재 초까지 언니가 방문한 위치들이 들어있다. 그니깐 나는 초별로 언니가 동생을 잡을수있는지 검사하는 것이다. 그래서 현재 초에 큐에서 나온것이 동생의 위치랑 같거나, 동생의 위치가 방문을 했던것이면, 현재 초를 출력해주는 것이다.

이게 말만으로는 되게 쉬웠는데, 생각하고 직접 행동에 옮기기에는 오래걸렸다.

다른 풀이보다 나름 코드가 깔끔하다고 생각하니 다른사람들도 참고하면 좋겠다^^

그럼 바위^^

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int time;
};

bool vis[500001][2];

int sum(int n) {
	return n * (n + 1) / 2;
}


int main()
{
	int N, K;//언니 위치 : N, 동생위치 : K
	cin >> N >> K;
	
	queue<Que> Q;
	Q.push({ N,0 });
	vis[N][0] = true;
	
	int answer = -1, i = 0;
	int nk;

	while (1) {
		int size = Q.size();
		nk = K + sum(i);
		//cout << "nk=" << nk<<endl;
		if (nk < 0 or nk>500000) {
			break;
		}
		while (size--) {
			auto cur = Q.front();
			//cout << "cur.x=" <<cur.x << endl;
			Q.pop();
			if (cur.x == nk or vis[nk][i%2]==true) {
				answer = i;
				goto ijsilver;
			}
			if (cur.x - 1 >= 0 and vis[cur.x - 1][(cur.time + 1) % 2] == false) {
				Q.push({ cur.x - 1,cur.time + 1 });
				vis[cur.x - 1][(cur.time + 1) % 2]=true;
			}
			if (cur.x + 1 <= 500000 and vis[cur.x + 1][(cur.time + 1) % 2] == false) {
				Q.push({ cur.x + 1,cur.time + 1 });
				vis[cur.x + 1][(cur.time + 1) % 2]=true;
			}
			if (cur.x *2 <= 500000 and vis[cur.x *2][(cur.time + 1) % 2] == false) {
				Q.push({ cur.x*2,cur.time + 1 });
				vis[cur.x*2][(cur.time + 1) % 2]=true;
			}
		}
		i++;

	}
ijsilver:
	cout << answer << endl;

}