백준 1697

백준 1697 : 숨바꼭질

1. bfs문제

2. 현재 위치가 N일때, 자식 노드는 N-1, N+1, 2*N임을 이용해서 BFS를 돈다.

3. 큐에 push 하는 조건을 잘 생각해 봐야 함

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, k;
int visited[100001];
int ans;
queue<int> q;


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

	cin>>n>>k;
	
	if(n==k) {
		cout<<0<<'\n';
		exit(0);
	}
	
	q.push(n);
	visited[n]=0;
	while(q.size()) {
		int now = q.front();
		q.pop();
		
		int n1 = now+1;
		int n2 = now-1;
		int n3 = now*2;	
		
		if(n1<100001 && !visited[n1]) {
			visited[n1] = visited[now]+1;
			q.push(n1);
		}
		if(n2>=0 && !visited[n2]) {
			visited[n2] = visited[now]+1;
			q.push(n2);
		}
		if(n3<100001 && !visited[n3]) {
			visited[n3] = visited[now]+1;
			q.push(n3);
		}
	}	
	
	
	cout<<visited[k]<<'\n';;
	
	return 0;
}