글 읽기 - 방문체크를 해주는 시점에 따라 결과가 달라집니다 ..!!

hoxymola 3년 전 0

0-1 BFS로 구현을 해봤습니다.

아래에 주석처리 된 코드는 push를 할때 방문체크를 해주었는데 제출하면 틀렸습니다가 나오고

위의 주석처리가 안된 코드는 똑같은 코드를 pop할때 방문체크를 하도록 바꿨더니 (놀랍게도) 맞았다고 나옵니다.

왜 이런 결과가 나오는지 너무 궁금합니다. ㅠ.ㅠ 도와주세요

#include <stdio.h>
#define QS 10000000

typedef struct node {
	int n;
	int d;
}node;
node QUEUE[QS];
int front = QS / 2;
int back = QS / 2;
node pop(void) {
	return QUEUE[++front];
}
void bpush(int n, int d) {
	QUEUE[++back].n = n;
	QUEUE[back].d = d;
}
void fpush(int n, int d) {
	QUEUE[front].n = n;
	QUEUE[front--].d = d;
}
int VST[100001];
int main(void) {
	int N, K;

	scanf("%d%d", &N, &K);
	bpush(N, 0);
	while (front != back) {
		node cur = pop();

		if (VST[cur.n])
			continue;
		VST[cur.n] = 1;

		if (cur.n == K) {
			printf("%d\n", cur.d);
			break;
		}

		if (0 <= cur.n - 1) 
			bpush(cur.n - 1, cur.d + 1);
		if (cur.n + 1 <= 100000)
			bpush(cur.n + 1, cur.d + 1);
		if (2 * cur.n <= 100000)
			fpush(2 * cur.n, cur.d);
	}

	return 0;
}

/*#include <stdio.h>
#define QS 10000000

typedef struct node {
	int n;
	int d;
}node;
node QUEUE[QS];
int front = QS / 2;
int back = QS / 2;
node pop(void) {
	return QUEUE[++front];
}
void bpush(int n, int d) {
	QUEUE[++back].n = n;
	QUEUE[back].d = d;
}
void fpush(int n, int d) {
	QUEUE[front].n = n;
	QUEUE[front--].d = d;
}
int VST[100001];
int main(void) {
	int N, K;

	scanf("%d%d", &N, &K);
	bpush(N, 0);
	VST[N] = 1;
	while (front != back) {
		node cur = pop();

		if (cur.n == K) {
			printf("%d\n", cur.d);
			break;
		}

		if (0 <= cur.n - 1 && !VST[cur.n - 1]) {
			bpush(cur.n - 1, cur.d + 1);
			VST[cur.n - 1] = 1;
		}
		if (cur.n + 1 <= 100000 && !VST[cur.n + 1]) {
			bpush(cur.n + 1, cur.d + 1);
			VST[cur.n + 1] = 1;
		}
		if (2 * cur.n <= 100000 && !VST[2 * cur.n]) {
			fpush(2 * cur.n, cur.d);
			VST[2 * cur.n] = 1;
		}
	}

	return 0;
}*/

shg9411 3년 전 1

현재 코드에서 fpush가 이뤄지는 위치가 잘못되었습니다.

hoxymola 3년 전 0

VST에 현재 위치에 도착한 가장 빠른 시간을 넣어서 해결했습니다 ,,

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

문제

문제

출처

ICPC

방문체크를 해주는 시점에 따라 결과가 달라집니다 ..!!

hoxymola 3년 전 0

shg9411 3년 전 1

hoxymola 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말