[BOJ] 1697 숨바꼭질(BFS)

1. 문제

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

2. 아이디어

최단거리를 찾는 문제이므로 BFS를 이용하여 해결하였다.

BFS문제를 풀 때,

• 다음 방문할 위치가 범위를 벗어나지 않는지
• 다음 방문할 위치를 아직 방문하지 않았는지

확인하고 두 조건에 모두 부합한다면 다음 위치를 큐에 넣고 방문처리를 한다.

3. 풀이과정

1) ⭕RIGHT⭕

• 코드

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

int visited[100001];
int dist[100001]; // 얼마만큼 걸려서 갔는지 표시

void BFS(int pos) {
	queue<int> q;
	q.push(pos);
	visited[pos] = 1;

	while (!q.empty()) {
		int current_pos = q.front();
		q.pop();

		if ((current_pos - 1 >= 0) && (visited[current_pos - 1] == false)) {
			q.push(current_pos - 1);
			visited[current_pos - 1] = true;
			dist[current_pos - 1] = dist[current_pos] + 1;

		}
		if ((current_pos + 1 <= 100000) && (visited[current_pos + 1] == false)) {
			q.push(current_pos + 1);
			visited[current_pos + 1] = true;
			dist[current_pos + 1] = dist[current_pos] + 1;
		}
		if ((current_pos * 2 <= 100000) && (visited[current_pos * 2] == false)) {
			q.push(current_pos * 2);
			visited[current_pos * 2] = true;
			dist[current_pos * 2] = dist[current_pos] + 1;
		}
	}
}

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

	int N, K;
	cin >> N >> K;

	visited[N] = 1;
	dist[N] = 0;

	BFS(N);

	cout << dist[K];
	return 0;
}