글 읽기 - [C언어] 틀린 이유 - 게시판 반례 확인

vorutesv 3년 전 0

게시판의 반례를 찾아 확인 했을 때도 이상이 없었는데,

제출하면 틀리게 나와서 도저히 모르겠습니다.

도와 주시면 감사하겠습니다.

#include <stdio.h>
#include <string.h>

#define MAX	50+1

int T, N, M, K;
int map[MAX][MAX] = {0, };
struct QUEUE {
	int x;
	int y;
};

struct QUEUE queue[MAX*MAX];
int visit[MAX][MAX] = {0, };
int rp, wp;
int cnt = 0;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void enqueue(int x, int y)
{
	queue[wp].x = x;
	queue[wp].y = y;
	wp++;
}

struct QUEUE dequeue()
{
	return queue[rp++];
}

int empty()
{
	return rp == wp;
}

void BFS(int x, int y)
{
	enqueue(x, y);
	visit[x][y] = 1;

	while(!empty())
	{
		struct QUEUE cur = dequeue();
		map[cur.x][cur.y] = 0;
		for(int i=0; i<4; i++)
		{
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];

			if(nx < 0 || nx >= M || visit[nx][ny] == 1) continue;
			if(ny < 0 || ny >= N || visit[nx][ny] == 1) continue;
			if(map[nx][ny] == 1 && visit[nx][ny] != 1)
			{
				visit[nx][ny] = 1;
                enqueue(nx, ny);
			}
		}
	}
}

int main()
{
	scanf("%d", &T);
    while(T--)
	{
		int x, y;
        cnt = 0;

		scanf("%d %d %d", &M, &N, &K);
		wp = rp = 0;
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        memset(queue, 0, sizeof(queue));
		for(int j=0; j<K; j++) {
			scanf("%d %d", &x, &y);
			map[x][y] = 1;
		}

		for(int jj=0; jj<N; jj++) {
			for(int kk=0; kk<M; kk++) {
				if(map[kk][jj] == 1 && visit[kk][jj] != 1) {
					BFS(kk, jj);
					cnt++;
				}
			}
		}
		printf("%d\n", cnt);
	}

	return 0;
}

seico75 3년 전 0

MAX*MAX = 50+1*50+1 = 50 + 50 + 1 = 101

sizeof(queue) = 8 * 101 = 808

입니다.

#define MAX (50+1)

으로 하거나

const int MAX = 50 + 1;

constexpr int MAX = 50 + 1;

이런 식으로 하셔야 합니다.

또한 52 라인에서 ny 의 범위는 확인이 안되서...

if ( nx < 0 || nx >= M || ny < 0 || ny >= 0 || visit[nx][ny] == 1) 이런식이 되어야 합니다.

물론 이래저래 해서 답에는 영향을 주지는 않습니다.

vorutesv 3년 전 0

답변 감사합니다.

MAX*MAX = 50+1*50+1 = 50 + 50 + 1 = 101

요 라인 때문에 그랬네요.

지금 보니 왜이렇게 했을까 한심합니다.

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

문제

문제

출처

ICPC

[C언어] 틀린 이유 - 게시판 반례 확인

vorutesv 3년 전 0

seico75 3년 전 0

vorutesv 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말