글 읽기 - vector 문제??

olbbemi 6년 전 0

똑같은 코드인데 단순히 배열이냐 vector 를 이용했냐 차이뿐입니다.

배열로 풀면 맞고 벡터를 쓰면 36%쯤에서 계속 런타임에러가 발생하는데.

몇번돌려본결과 메모리 문제는 아닌것으로 판별났습니다. 코드차이는 배열이냐 벡터냐 차이밖에없는데

왜인지 도무지 모르겠습니다

// 벡터를 이용하여 런타임에러 발생, 37번 줄에 < 대신에 <= 쓰면 AC 뜸
#include <cstdio>
#include <vector>
#define INF 99999999
using namespace std;

vector< vector< pair<int, int> > > G(1001);
vector<int> D(1001);
vector<int> Check(1001);

int main()
{
	int a, b, c, N, M, S, E;
	scanf("%d%d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
	}

	scanf("%d%d", &S, &E);

	for (int i = 0; i <= N; i++)
	{
		D[i] = INF;
		Check[i] = false;
	}

	D[S] = 0;
	for (int i = 1; i <= N - 1; i++)
	{
		int Min = INF;
		int index = -1;
		for (int j = 1; j <= N; j++)
		{
			if (Check[j] == false && D[j] < Min)
			{
				Min = D[j];
				index = j;
			}
		}

		Check[index] = true;

		for (int j = 0; j < G[index].size(); j++)
			if (D[G[index][j].first] > G[index][j].second + D[index])
				D[G[index][j].first] = G[index][j].second + D[index];
	}

	printf("%d", D[E]);
	return 0;
}

// AC 코드
#include <cstdio>
#include <vector>
#define INF 99999999
using namespace std;

vector< vector< pair<int, int> > > G(1001);
int D[1001];
bool Check[1001];

int main()
{
	int a, b, c, N, M, S, E;
	scanf("%d%d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
	}

	scanf("%d%d", &S, &E);

	for (int i = 1; i <= N; i++)
	{
		D[i] = INF;
		Check[i] = false;
	}

	D[S] = 0;
	for (int i = 1; i <= N - 1; i++)
	{
		int Min = INF;
		int index = -1;
		for (int j = 1; j <= N; j++)
		{
			if (Check[j] == false && D[j] < Min)
			{
				Min = D[j];
				index = j;
			}
		}

		Check[index] = true;

		for (int j = 0; j < G[index].size(); j++)
			if (D[G[index][j].first] > G[index][j].second + D[index])
				D[G[index][j].first] = G[index][j].second + D[index];
	}

	printf("%d", D[E]);
	return 0;
}

두 코드 다 index가 -1이 되는 경우가 있습니다. assert(index >=0)를 하시면 둘 다 런타임 에러가 발생하는 걸 보실 수 있으실 겁니다. 다만 배열을 사용했을 때는 -1번 인덱스를 참조했을 때 세그폴트가 안나고 에러를 묵인하기 때문입니다. 물론 배열의 -1번 인덱스를 참조하는 건 엄연한 에러이기 때문에 여기서 잘 돌아간다고 다른 환경에서 잘돌아간다는 보장은 절대 없습니다.

olbbemi 6년 전 0

아 그렇군요.. 저번에 답해주신거때문에 틀린이유는 알았는데 또다른걸 배워가네요.

감사합니다.

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

문제

문제

출처

ICPC

vector 문제??

olbbemi 6년 전 0

lvalue 6년 전 0

olbbemi 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말