[백준 - 1697] 숨바꼭질

#include <iostream>
#include <queue>
using namespace std;
#define MAX 100'000
bool arr[100'001] = { 0, };
int N,K;

queue<pair<int,int>> q;
int BFS(const int & start)
{
	if (N == K) return 0;

	q.push({ start, 0});

	int A, B, C;
	while (q.empty() == false)
	{
		int data = q.front().first;
		int time = q.front().second + 1;

		A = data - 1;	B = data + 1;	C = data * 2;

		if (0 < A && arr[A] == false)
		{
			q.push({ A, time });
			arr[A] = true;
		}
		if (B < MAX && arr[B] == false)
		{
			q.push({B, time });
			arr[B] = true;
		}
		if (C <= MAX && arr[C] == false)
		{
			q.push({C, time });
			arr[C] = true;
		}
	
		if (A == K || B == K || C == K) return time;
		q.pop();
	}

	return -1;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K;
	cout << BFS(N);

	return 0;
}

---

||사고 과정

동적 프로그래밍을 사용하기엔 경우의 수가 너무 많았고

그리디라기엔 바로 나오는게 정답이 아니기에 제외했고

간단한 완전삼진트리??를 탐색하는 그래프로 생각하고 탐색 단계가 곧 시간이기에 BFS를 사용했다.

 

어찌어찌 N에서 K까지는 갈수 있었지만 처음에 용량 초과로 나와

방문처리용 배열로 중복되는 값들을 제외시켰다.

 

하지만 이번엔 단계를 구하는 논리가 부족했었다.

그래서 이부분은 다른 사람의 코드를 참고했다ㅠ

 

제일 나아보였던게 pair로 단계를 저장하여 사용하는것이여서

가져와 정답을 맞추었다.

---

||사용 기법

• BFS

---

||풀면서 느낀 것

• 예외 처리

값이 나올 수 있는 예외를 잘 생각하면서 if문을 작성하자

• BFS의 단계 확인

BFS는 아무래도 단계를 구하는게 많다보니 이번에 여러 방법으로 구하는 방법들을 알았다.

pair가 내 기준에서는 가장 깔끔했고, 단계전용 배열을 만들어 사용하는것도 있었다.

---

||새로 알게 된것

• Pair의 생성

make_pair로만 생성하는줄 알았지만 pair<int, int> a = {1, 2} 이런식으로도 가능!

그래서 이번에 pair의 큐에 push할 때 잘 사용했다.

queue<pair<int,int>> q;
q.push({1,3});

---

||나아 진것

• BFS 작성 속도

예전보다 빠르게 작성할 수 있게 됐다.