문제
풀이
큐를 이용해서 완전 탐색을 하는 코드이다. x-1, x+1, 2*x에 해당하는 값들을 queue에 넣고, 이미 넣었던 함수라면 어차피 반복되니 메모리를 사용하지 않기 위해 visit함수로 check를 해주면서 메모리를 절약해주었다. 완전탐색으로 원하는 값이 나올 때 depth를 출력하고 종료한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <queue>
using namespace std;
int main(){
int N, M;
scanf("%d %d", &N, &M);
queue<pair<int, int>> q;
q.push(make_pair(N, 0));
bool visit[100001];
for(int i = 0; i<100001; i++){
visit[i] = false;
}
visit[N] = true;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
if(x == M){
printf("%d\n", y);
return 0;
}
q.pop();
if(visit[x-1] == false && x-1 >= 0 && x-1 < 100001){
q.push(make_pair(x-1, y+1));
visit[x-1] = true;
}
if(visit[x+1] == false && x+1 >= 0 && x+1 < 100001){
q.push(make_pair(x+1, y+1));
visit[x+1] = true;
}
if(visit[2*x] == false && 2*x >= 0 && 2*x < 100001){
q.push(make_pair(2*x, y+1));
visit[2*x] = true;
}
}
}
