글 읽기 - 숨바꼭질 2 한번 봐주실수있을까요?

his130 6년 전 0

저는 기존 bfs 랑 다르게 아래처럼 큐에 모든 값들을 집어넣고,

처음 목표지점이 발견된 깊이보다 더 깊어지면 탐색을 종료하도록 설정했는데..

틀렸습니다가 나옵니다..

어떤 오류일까요?

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int dx[3] = { -1,1,2 };
int dist[100001];
long long cnt;
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);

	if (n == k)
	{
		printf("0\n1\n");
		return 0;
	}

	queue<int> q;
	dist[n] = 0;
	q.push(n);

	int size;
	int depth = -1;

	while (!q.empty())
	{
		size = q.size();
		depth++;

		// 정답이 있는 깊이보다 깊은 경우
		if (dist[k] != 0 && depth == dist[k] + 1)
		{
			break;
		}

		for (int t = 0; t < size; t++)
		{
			int now = q.front();
			q.pop();


			if (now == k)
			{
				cnt++;
			}

			for (int i = 0; i < 3; i++)
			{
				int next;
				if (i == 2)
				{
					next = now*dx[i];
				}
				else
				{
					next = now + dx[i];
				}
				
				if (next >= 0 && next <= 10000)
				{
					if (dist[next] != 0)
					{
						dist[next] = min(dist[next], dist[now] + 1);
					}
					else
					{
						dist[next] = dist[now] + 1;
					}
					
					q.push(next);
				}
			}
		}
	}

	printf("%d\n%lld\n", dist[k], cnt);

	return 0;
}

sgchoi5 6년 전 0

질문 검색하시면 힌트가 될만한 내용이 있습니다.. 저도 그 힌트보고 풀었습니다

his130 6년 전 0

일단 제가 조건문에서 next값을 혼동해서 실수했는데..

메모리 초과가 나오는데.. 어떤 힌트를 말씀하시는건가요?ㅠㅠ

sgchoi5 6년 전 0

아래 글에서 얻은 힌트입니다..

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

숨바꼭질 2 한번 봐주실수있을까요?

his130 6년 전 0

sgchoi5 6년 전 0

his130 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말