[백준 1697번 C/C++] 숨바꼭질

 

 

[백준 1697번 C/C++] 숨바꼭질

 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

 

 

해결전략

 

너비우선탐색, BFS

 

---

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, k; //n: 수빈 현재 점, k: 동생 점
queue<pair<int,int>> Q; // 첫 번째 원소는 위치, 두 번째 원소는 해당 위치에 도달하기까지 걸린 시간
vector<int> ch; //해당 위치를 방문했는지 여부를 체크

int minSec = 2147000000;

void BFS(int n, int k)
{
	//시작점인 수빈이의 위치와 초(sec)를 삽입하고 방문 처리
	Q.push({ n, 0 });
	ch[n] = 1;

	while (!Q.empty())
	{
		int x = Q.front().first;
		int sec = Q.front().second;
		Q.pop();

		//현재 위치가 목표인 동생의 위치와 같다면 지금까지 걸린 시간(sec)을 출력하고 함수를 종료
		if (x == k){
			cout << sec;
			return;
		}

		if (ch[x-1]==0 && 0 < x-1)
		{
			Q.push({ x - 1, sec + 1 });
			ch[x - 1] = 1;
		}
		if (ch[x+1]==0 && x+1 < k * 2)
		{
			Q.push({ x + 1, sec + 1 });
			ch[x + 1] = 1;
		}
		if (ch[x*2]==0 && x*2 < k * 2)
		{
			Q.push({ x * 2, sec + 1 });
			ch[x * 2] = 1;			
		}

	}
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;

	ch.resize(100000);//충분히 크게 잡아줘야 한다.

	BFS(n, k);

	return 0;
}

 

 

---

 

더 간결한 코드

 

#include <iostream>
using namespace std;

int min(int a, int b) {
	return a < b ? a : b;
}

int BFS(int n, int k)
{
	if (n <= k)
		return k - n;

	else if (n == 1)
		return 1;

	else if (n % 2)
		return 1 + min(BFS(n - 1, k), BFS(n + 1, k));

	else
		return min(n - k, 1 + BFS(n / 2, k));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;

	cout << BFS(n, k);
}

 

 

---

 

H3 중제목

본문내용넣기

 

 

 

 

 

---

 

마무리

마무리