[ 백준 - 1697 / BFS ] 숨바꼭질

1. 문제

---

 

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

 

 

 

 

2. 소스코드

---

1회차 - 2020/05/11

 

- 예전에 카카오?라인? 기출이 이것과 유사한 문제였던 것 같다.

- 완전 탐색을 통해 최솟값을 구하는 경우, 대게 dfs가 아닌 bfs문제이다. dfs는 잘못하면 터진다.

- 배열 크기에 유의

 

#include <cstdio>
#include <queue>
#define MAX 100000
using namespace std;
int subin, bro;
int visited[MAX+1];

void bfs() {
	queue<pair<int, int>> que;
	que.push({ subin,0 });
	visited[subin] = 1;
	while (!que.empty())
	{
		auto cur = que.front(); que.pop();
		int pos = cur.first;
		int depth = cur.second;
		if (pos == bro) {
			printf("%d", depth); return;
		}
		if (pos - 1 >= 0 and !visited[pos - 1]) {
			que.push({ pos - 1, depth + 1 });
			visited[pos - 1] = 1;
		}
		if (pos + 1 <= MAX and !visited[pos + 1]) {
			que.push({ pos + 1, depth + 1 });
			visited[pos + 1] = 1;
		}
		if (pos * 2 <= MAX and !visited[pos * 2]) {
			que.push({ pos * 2, depth + 1 });
			visited[pos * 2] = 1;
		}
	}
}

int main(void) {
	scanf("%d %d", &subin, &bro);
	bfs();
	return 0;
}