글 읽기 - 자꾸 틀렸습니다 라고 떠요

jjohye11 7년 전 0

어디가 틀린걸까요??

비쥬얼스튜디오에서는 5 17 넣었을 때 답 잘나옵니다..

#include <stdio.h>


int N, K; 
int visited[100000] = { 0, };
int rear = 0;
int front = 0;
int queue[50000];

void push(int input) {
	queue[rear+1] = input;
	rear++;
}

int pop() {
	int item = queue[front];
	front++;

	 return item;
}

int empty()
{
	if (front == rear)
		return 1;
	return 0;
}

int bfs()
{
	push(N);
	visited[N] = 1;

	while (empty() == 0)
	{
		int cur = pop();

		if (cur == K)
			return visited[cur]-1;

		if (cur - 1 >= 0 && visited[cur - 1] == 0) {
			push(cur - 1);
			visited[cur - 1] = visited[cur] + 1;
		}
		
		if (cur + 1 <= 100000 && visited[cur + 1] == 0) {
			push(cur + 1);
			visited[cur + 1] = visited[cur] + 1;
		}

		if (cur * 2 <= 100000 && visited[cur * 2] == 0) {
			push(cur * 2);
			visited[cur * 2] = visited[cur] + 1;
		}
	}

}

int main()
{
	scanf("%d %d", &N, &K);         

	printf("%d",bfs());

	return 0;
}

kalmiaa 7년 전 0

visited는 한번 방문하고 끝이 아니라,

더 낮은값이 오면 또 갱시해줘야 해요.

doomsdt 7년 전 0

BFS의 특성상 갱신할 필요는 없을것 같습니다.

5 17은 너무 안전한 테스트 케이스라서 여러가지 케이스의 경우를 생각해 보세요.

일단 0~100000이라서 visited는 100001까지 잡아줘야 하구요.

100000의 범위를 감당하기에 큐가 너무 작은 것 같네요.

더군다나 지금 구현하신 걸로는 pop 할 때마다 큐의 용량이 줄어들기 때문에..

rbdi3222 6년 전 0

void push(int input) {
queue[rear+1] = input;
rear++;
}

여기 보시면 시작 push는

void push(int input) {
queue[rear] = input;
rear++;
}

로 바꾸셔야할 것 같습니다. rear + 1로 해버린 후 pop 해버리시면

int pop() {
int item = queue[front];
front++;
return item;
}

push 에서 queue[1]에 입력값이 들어갔기 때문에 int cur = pop(); 여기서는 queue[0] 값을 받아와서 문제가 됫던거 같습니다~

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

문제

문제

출처

ICPC

자꾸 틀렸습니다 라고 떠요

jjohye11 7년 전 0

kalmiaa 7년 전 0

doomsdt 7년 전 0

rbdi3222 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말