[백준1697] 숨바꼭질 (C++)

📌 문제

BOJ 바로가기

수빈이가 n, 동생이 k의 위치에 있을 때 수빈이가 동생을 찾기 위해서 몇 번 이동해야 하는지 구해야 한다.

🗡 풀이

조심해야 할 부분

• 수빈이와 동생이 같은 위치에 있을 경우

go[3]배열을 선언해 한 칸 앞으로 갈 경우, 한 칸 뒤로 갈 경우, 현재 위치의 두 배가 되는 위치로 점프할 경우를 한 번에 처리해줬다.

🚩 소스코드

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

queue<int> q;
int dist[100001] = { 0 };
bool visited[100001] = { false };
int n, k;
int ans;

void bfs() {
	q.push(n);
	visited[n] = true;
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		int go[3] = { n - 1, n + 1, 2 * n }; // 한 칸 앞, 한 칸 뒤, 두배 점프
		for (int i = 0; i < 3; i++) {
			int nx = go[i];
			if (0 <= nx && nx <= 100000 && !visited[nx]) {
				q.push(nx);
				visited[nx] = true;
				dist[nx] = dist[n] + 1;
			}
			if (nx == k) {
				ans = dist[nx];
				return;
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> k;
	if (n == k) {
		cout << '0';
	}
	else {
		bfs();
		cout << ans;
	}
}