글 읽기 - 반례를 못찾겠습니다ㅠㅠ

bbbb56146 5년 전 0

BFS로 풀었는데요, 게시판에 나와있는 반례 모두 맞는데 틀렸다고 나옵니다..!

순간이동이 첫 조건인데 뭐가 문제일까요 ㅠㅠ

//////////////리스트로 큐 구현하기////////////
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
	int data;
	struct node* next;
}node;
typedef struct queue {
	node* front;
	node* rear;
	int count;
}queue;
void init_queue(queue* q) {
	q->front = q->rear = NULL;
	q->count = 0;
}
void enqueue(queue* q, int x) {
	node* new = (node*)malloc(sizeof(node));
	new->data = x;
	new->next = NULL;
	if (empty(q)) {//비었으면 1 리턴
		q->front = new;
	}
	else {
		q->rear->next = new;
	}
	q->rear = new;
	q->count++;
}
int dequeue(queue* q) {
	if (empty(q)) {
		return -1;
	}
	node* tmp = q->front;
	int n = tmp->data;
	q->front = q->front->next;
	free(tmp);
	q->count--;
	return n;
}
int size(queue* q) {
	return q->count;
}
int empty(queue* q) {
	return (q->count == 0);
}
int front(queue* q) {
	if (empty(q)) return -1;
	return q->front->data;
}
int back(queue* q) {
	if (empty(q)) return -1;
	return q->rear->data;
}
///숨바꼭질 3코드 //
int visit[1000001];//탐색 깊이 뜻함
void init_visit() {
	for (int i = 0; i <= 1000000; i++) {
		visit[i] = -1;//방문 안했을때 -1
	}
}
int BFS(int n, int k, queue* q) {
	enqueue(q, n);
	visit[n] = 0;
	while (!empty(q)) {//큐가 비어있기 전까지 반복
		int now = dequeue(q);//큐에서 빼서 탐색
		if (now == k) {
			return visit[now];
		}
		if (now * 2 <= 1000000 && visit[now * 2] == -1) {
			//방문안했고 범위안이면
			enqueue(q, 2 * now);//큐에 넣음
			visit[2 * now] = visit[now];
		}
		if (now + 1 <= 1000000 && visit[now + 1] == -1) {
			//방문안했고 범위안이면
			enqueue(q, now + 1);//큐에 넣음
			visit[now + 1] = visit[now] + 1;
		}
		if (now - 1 >= 0 && visit[now - 1] == -1) {
			//방문안했고 범위안이면
			enqueue(q, now - 1);//큐에 넣음
			visit[now - 1] = visit[now] + 1;
		}
	}
}
int main() {
	int N, K;
	queue* q = (queue*)malloc(sizeof(queue));
	init_queue(q);//큐 초기화
	scanf("%d %d", &N, &K);
	init_visit();//visit 배열 초기화
	printf("%d", BFS(N, K, q));
	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다ㅠㅠ

bbbb56146 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말