백준 1697번 숨바꼭질

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

1697번: 숨바꼭질

 

 

 

 

 

<접근방법>

탐색 문제입니다.

bfs로 풀었습니다.

범위 체크와 방문 체크가 필요합니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

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

struct point {
	int x, cnt;
};

int n, k;
bool visit[100001];

queue<point> q;

void bfs() {
	q.push({ n, 0 });
	visit[n] = true;

	while (!q.empty()) {
		int x = q.front().x;
		int cnt = q.front().cnt;
		int nx;
		q.pop();

		if (x == k) {
			cout << cnt << '\n';
			return;
		}
		nx = x + 1;
		if (0 <= nx && nx <= 100000 && !visit[nx]) {
			q.push({ nx, cnt + 1 });
			visit[nx] = true;
		}
		nx = x - 1;
		if (0 <= nx && nx <= 100000 && !visit[nx]) {
			q.push({ nx, cnt + 1 });
			visit[nx] = true;
		}
		nx = x * 2;
		if (0 <= nx && nx <= 100000 && !visit[nx]) {
			q.push({ nx, cnt + 1 });
			visit[nx] = true;
		}
	}
}

int main() {
	cin >> n >> k;

	bfs();

	return 0;
}