글 읽기 - C) 1%에서 틀렸습니다 나오는데 진짜 이유를 모르겠네요;;;

gue707 3년 전 0

모든 예제 다 잘나오는데

1% 뜨고 틀렸습니다 뜹니다..

상하좌우 모두 체크한거 같은데

반례가 있을까요??

입력받을때 getchar썻다가 이게 잘못인줄 알아서 매우 단순하게 고쳤지만 getchar문제가 아니었네요,,,

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int map[100][100], n, m, cnt = 0;
int check[100][100] = { 0 };
int dis[100][100] = { 0 };

typedef struct queue
{
	int q[100][2];
	int f, r;
}que;

void init(que* x) {
	x->f = x->r = -1;
}

int isEmpty(que x) { return x.f == -1; }

void push(que* x, int p, int q)
{
	if (isEmpty(*x))
	{
		x->q[++x->r][1] = q;
		x->q[x->r][0] = p;
		x->f = x->r;
	}
	else {
		x->q[(1 + x->r) % 100][1] = q;
		x->r = (1 + x->r) % 100;
		x->q[x->r][0] = p;
		if (x->r == x->f) x->f = (x->f + 1) % 100;
	}
}

int* pop(que* x)
{
	int* tmp = x->q[x->f];
	if (x->r == x->f) x->r = x->f = -1;
	else
	{
		x->f = (x->f + 1) % 100;
	}
	return tmp;
}

int bfs(int x, int y)
{
	que q; init(&q);
	push(&q, x, y);
	while (!isEmpty(q))
	{
		int* t = pop(&q); int a = t[0], b = t[1];
		check[b][a] = 1;
		if (a + 1 < m && map[b][a + 1] && !check[b][a + 1])
		{
			push(&q, a + 1, b);
			dis[b][a + 1] = 1 + dis[b][a];
		}
		if (a - 1 >= 0 && map[b][a - 1] && !check[b][a - 1])
		{
			push(&q, a - 1, b);
			dis[b][a - 1] = 1 + dis[b][a];
		}
		if (b + 1 < n && map[b + 1][a] && !check[b + 1][a])
		{
			push(&q, a, b + 1);
			dis[b + 1][a] = 1 + dis[b][a];
		}
		if (b - 1 >= 0 && map[b - 1][a] && !check[b - 1][a])
		{
			push(&q, a, b - 1);
			dis[b - 1][a] = 1 + dis[b][a];
		}
	}
}

int main() {

	char k,tmp;
	scanf("%d %d%c", &n, &m,&tmp); 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%c", &k); map[i][j] = k - '0';
		}
		scanf("%c", &tmp);
	}
	bfs(0, 0);
	printf("%d", dis[n - 1][m - 1] + 1);
	return 0;
}

djm03178 3년 전 2

BFS는 큐에서 뺀 뒤가 아닌 큐에 넣을 때 방문 표시를 해야 중복 방문이 일어나지 않습니다. 그 외에도 큐 안에 동시에 있는 원소가 100개 이하로 유지될 수 있다는 보장이 있는지 잘 모르겠네요.

gue707 3년 전 0

말씀대로 큐에서 pop할때 방문처리한게 문제였네요,,ㅋㅋㅋ

넣을때 해주니까 바로 됐습니다.

100개는 안고쳐도 되긴했지만, 100개 이하로 유지된다는 보장이 없어서 유념해야할 부분이 또 있는거 같아요.

감사합니다!!!

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

문제

문제

출처

ICPC

C) 1%에서 틀렸습니다 나오는데 진짜 이유를 모르겠네요;;;

gue707 3년 전 0

djm03178 3년 전 2

gue707 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말