처음에는 K가 될 수 있는 가능성은 K+1, K-1, K/2 이렇게 3가지 경우라 생각해서 범위를 N이 K+1작은 경우안으로 잡았었다. 하지만 결과는 틀렸습니다. …이유는 K가 N보다 작을 경우를 놓쳤기 때문이다. 5에서 17을 찾아가는 경우와 같이 K가 더 큰 경우에는 상관이 없지만 17에서 5를 찾아가야 할 경우도 있다. 따라서 이렇게는 안되고 depth를 계산해 구해줘야 한다.
다른 풀이를 보면 K+1, K-1, K*2를 if문으로 확인했는데 나는 다른 인접한 4방향을 탐색하는 bfs풀이와 비슷하게 해결하였다. 이 경우는 3가지 경우가 있으므로 함수를 하나 만들어 3가지 경우를 탐색해주었다.
int next(int i, int p) {
switch (i) {
case 0:
return p+1;
break;
case 1:
return p-1;
break;
case 2:
return p*2;
break;
default:
break;
}
return -1;
}
...
for(int i=0; i<3; i++) {
int n = next(i, p);
if(n<0 || n==N || n>100000 || visited[n]) continue;
if(n == K) {
printf("%d\n", depth+1);
queue<int> empty;
q = empty;
return;
}
visited[n] = true;
q.push(n);
}
항상 범위에 주의하자.. n>100000를 추가해주지 않아 런타임에러… ㅜ_ㅜ
풀이보기
```c++
#include <iostream>
#include <queue>
using namespace std;
int N, K;
bool visited[100002];
int next(int i, int p) {
switch (i) {
case 0:
return p+1;
break;
case 1:
return p-1;
break;
case 2:
return p*2;
break;
default:
break;
}
return -1;
}
void bfs() {
if(N == K) {
printf("0\n");
return ;
}
queue<int> q;
q.push(N);
visited[N] = true;
int depth = 0;
while (!q.empty()) {
int qSize = q.size();
while (qSize--) {
int p = q.front(); q.pop();
for(int i=0; i<3; i++) {
int n = next(i, p);
if(n<0 || n==N || n>100000 || visited[n]) continue;
if(n == K) {
printf("%d\n", depth+1);
queue<int> empty;
q = empty;
return;
}
visited[n] = true;
q.push(n);
}
}
depth++;
}
}
int main(int argc, const char * argv[]) {
scanf("%d %d", &N, &K);
bfs();
return 0;
}
```