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

bfs를 문제를 활용해서 풀면 된다. 

 

#접근방법

1. 방문 배열 100001개 생성 후 큰 값으로 초기화

2. 수빈이의 현재 위치 queue에 push. 

3. queue에 들어간 수빈이의 현재 위치에서 갈 수 있는 경로는 현재 값에서 -1 , +1, *2 이다 

현재 위치에서 3가지 방향의 값을 연산하여 해당 인덱스의 visited값을 갱신해간다. 

4. queue에 값이 있을 동안 반복문을 돌리며 수빈의 위치와 동생의 위치가 동일하다면 해당 인덱스의 visitied값을 출력하고 종료한다. 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std; 
int n, k;
int visited[100001]; 
queue <int> q;
void bfs() {
	int y, x;
	while (!q.empty()) {
		x = q.front();
		q.pop(); 	
		if (x == k) {
			cout << visited[x]; 
			exit(0);
		}
		if (x + 1 <= 100000 && visited[x]<visited[x + 1]) {
			visited[x + 1] = visited[x]+1;
			q.push( x + 1);
		}
		if (x - 1 >= 0 && visited[x] < visited[x - 1]) {
			visited[x - 1] = visited[x]+1; 
			q.push( x - 1 );
		}		
		if (x * 2 <= 100000&& visited[x] < visited[x*2]) {
			visited[x * 2] = visited[x]; 
			q.push( x * 2);
		}		
	}	
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k; 
	if (n == k) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i <= 100000; i++) visited[i] = 987654321; 
	visited[n] = 0; 
	q.push({ n });
	bfs(); 
}

13549번: 숨바꼭질 3