13913 숨바꼭질4 (메모리 초과, 틀렸습니다 유의사항)

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

숨바꼭질 4 성공스페셜 저지

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

6450

2220

1551

33.850%

문제

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

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

입력

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

출력

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4 5 10 9 18 17

예제 입력 2 복사

5 17

예제 출력 2 복사

4 5 4 8 16 17

출처

• 문제를 만든 사람: baekjoon

 

<개인풀이>

1. 1697 숨바꼭질과 동일하지만 바꿔야 하는부분

 

2. 추적을 위해 check 값을 0,1 이아닌 int형으로 정의, 이유는 해당 값의 인덱스를 통해 전 값을 추적할수 있기때문,

 

3. 주의 해야 할점, check 초기값을 -1로 해놓음, unsigned 로 해놓았다가, 방문하지 않음을 0으로 하면,

 (0, n) 입력시 0 값의 인덱스를 찾아가면 양의 정수값 1이있고, 1은 또 인덱스[2]의 값이기때문에 무한루프를 돔.

 그러면 메모리 초과가 일어난다. (아래 그림처럼)

 

4. 추적값을 편하게 출력해주면 됨.

 

#include<stdio.h>
#include<queue>
#include<stack>
#include<cstring>


int check[100001];
using namespace std;
int ans;
int main(void)
{
	memset(check, -1, sizeof(check));
	int n, m; // n 수빈위치, m 동생 위치
	int count = 0;
	scanf("%d %d", &n, &m);

	if (n == m)
	{
		printf("%d\n", 0);
		printf("%d\n", n);
		return 0;
	}
	queue<pair<int,int>> q;

	q.push(make_pair(n, count));

	int location = 0;
	
	while (!q.empty())
	{
		location = q.front().first;
		count = q.front().second;
		q.pop();
		if ((location - 1) >= 0 && check[location - 1]==-1)
		{
			int temp_count = count + 1;
			int temp_location = location - 1;
			check[temp_location] = location;
			if (temp_location == m)
			{
				printf("%d\n",temp_count);
				break;
			}
			q.push(make_pair(temp_location, temp_count));
			 
		}

		if ((location + 1) <= 100000 && check[location + 1]==-1)
		{
			int temp_count = count + 1;
			int temp_location = location + 1;
			check[temp_location] = location;
			if (temp_location == m)
			{
				printf("%d\n", temp_count);
				break;
			}
			q.push(make_pair(temp_location, temp_count));

		}

		if ((location * 2) <= 100000 && check[location * 2]==-1)
		{
			int temp_count = count + 1;
			int temp_location = location * 2;
			check[temp_location] = location;
			if (temp_location == m)
			{
				printf("%d\n", temp_count);
				break;
			}
			q.push(make_pair(temp_location, temp_count));

		}
	}
	while (!q.empty())
	{
		q.pop();
	}
	stack<int> reverse_count;
	reverse_count.push(m);
	while (n != m)
	{
		reverse_count.push(check[m]);
		m  = check[m];

	}

	while (!reverse_count.empty())
	{
		printf("%d ", reverse_count.top());
		reverse_count.pop();
	}
	return 0;
}