13549 숨바꼭질3

숨바꼭질 3 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	5255	1608	1021	28.322%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

엄청난 고전을 했다.

처음엔 그냥 BFS로 풀었다가 틀렸다.

이유는 Teleport할때 비용이 0이기 때문에 그것을 제대로 계산안해줘서

인자로 누적시켜서 해결했다.

근데 또 틀렸다.

반례를 찾아보니 1 16일때 틀렸었던거 같다.

내가 조건문을 +1, -1, *2 순으로 비교했는데

1에서 2로간다고 치면 +1부분을 먼저 체크하고 방문처리를 해버려서 *2체크가 안되는 상황이었던 것이다.

그래서 *2, +1, -1순으로 바꾸었다.

여기서부터 엄청나게 틀렸다.

더이상 고칠게 없다고 판단했고, 내가 생각한 모든 반례가 다 알맞게 나왔기 때문이다.

계속 44%에서 틀렸는데, 이걸로 한 2시간은 고민한것 같다.

*2, +1, -1 순으로 if문을 체크해서 que에 넣으면

2가 나오지만

*2, -1, +1 순으로 if문을 체크하면

1이 나온다.

작아졌다가 2배수하는게 더 빠른 경우가 있는데 +1을 먼저함으로써 방문처리를 해버려가지고

틀렸던 것이다.

BFS에서 if문의 순서도 중요하다 는 것을 꼭 기억하자

#include <iostream>

#include <queue>

#include <cstdlib>

#include <string>

#include <cstring>

using namespace std;

#define MAX 100001

int n; // 나의 현재 위치

int k; // 동생의 현재 위치

bool visited[MAX];

struct Data

{

int pos;

int movedByTeleport;

};

queue<Data> que;

int bfs();

int main()

{

//1초 후에 x-1 x+1 0초 후에 2*X까지 이동이 가능하다.

freopen("input.txt","r", stdin);

ios::sync_with_stdio(false);

cin.tie(0);

memset(visited, false, sizeof(visited));

cin >> n;

cin >> k;

que.push({n, 0});

visited[n] = true;

cout << bfs();

return 0;

}

int bfs()

{

int step_size;

int total_size = 0;

Data d;

while (!que.empty())

{

step_size = que.size();

for (int i = 0; i < step_size; ++i)

{

d = que.front();

que.pop();

if (d.pos == k)

{

return total_size - d.movedByTeleport;

}

if (d.pos * 2 < MAX && !visited[d.pos * 2]) // 비용이 작은거 먼저 처리

{

que.push({d.pos * 2, d.movedByTeleport + 1});

visited[d.pos * 2] = true;

}

if (d.pos + 1 < MAX && !visited[d.pos + 1])

{

que.push({d.pos + 1, d.movedByTeleport});

visited[d.pos + 1] = true;

}

if (d.pos - 1 >= 0 && !visited[d.pos - 1])

{

que.push({d.pos - 1, d.movedByTeleport});

visited[d.pos - 1] = true;

}

}

total_size++;

}

return -1;

}