글 읽기 - 2606번 바이러스 어디서 런타임 에러가 나는지 모르겠습니다

dearsanta 7년 전 1

배열 범위를 초과하지는 않을 것 같습니다.

예제에 대해 출력은 올바르게 나오는 것 같습니다.

도와주세요 ㅜㅜ

2차원 배열을 1차원 처럼 사용하였고 비트에 마스크를 입혀 공간복잡도를 V(정점)^2 / 8 로 줄이려고 하는 중 입니다.

#include <cstdio>
#define MAX 100
#define SIZE ((MAX + 7) >> 3)
#define OFFSET(a,b,c) a * b + c

unsigned char list[SIZE]; // 방문여부
unsigned char visited[SIZE]; // 2차원 인접 행렬 표현
int cnt = -1;
int x_size = 0;

using namespace std;

// 방문 체크
void setVisit(int v)
{
	visited[v >> 3] |= (1 << (v & 7));
}

// 방문확인
int isVisit(int v)
{
	return visited[v >> 3] & (1 << (v & 7));
}

// 2차원 배열  x y 를 1로
void setList(int x,int y,int x_size)
{
	int offset = OFFSET(y, x_size, x);
	list[offset >> 3] |= (1 << (offset & 7));
}

// arr[x][y] 가 1 이나 0인지 확인
int getList(int x,int y,int x_size)
{
	int offset = OFFSET(y, x_size, x);
	return (list[offset >> 3] & (1 << (offset & 7))) ? 1 : 0;
}

// DFS
void dfs(int here)
{
	cnt += 1;
	setVisit(here);

	for (int i = 1; i < x_size; i++)
		if (getList(here, i, x_size) && !isVisit(i))
			dfs(i);

}

int main()
{
	int n, m, i;

	scanf("%d %d", &n,&m);

	x_size = n + 1;
	int v, w;

	for (i = 0; i < m; i++)
	{
		scanf("%d %d", &v, &w);
		setList(v, w, x_size);
		setList(w, v, x_size);
	}

	dfs(1);

	printf("%d",cnt);

	return 0;
}

zlzmsrhak 7년 전 0

먼저 반례부터 제시하면,

100

31 2

28번째 줄에서 offset의 값이 최대 1만 정도까지 가능합니다. 그래서 배열 범위를 초과하는 것이 맞습니다.

추가로 언급해드리면, 4번째 줄 처럼 매크로 선언을 하게 되면 OFFSET(3+2, 2, 1) 이 8이 되는 기적을 보실 수 있습니다.

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

문제

문제

출처

ICPC

2606번 바이러스 어디서 런타임 에러가 나는지 모르겠습니다

dearsanta 7년 전 1

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말