공부합시다

memset의 두번째 인자는 char형(1byte)로 인식된다.

int형 배열 선언하고 0으로 초기화 하려고 memset을 사용하다가 알게 된 사실;;
sizeof(int)를 사용해서 해결했다.

신고

max_size()가 넘어가면 이런 오류가 나오는구나.

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

2GB 정도의 텍스트파일을 라인별로 파씽해서 vector에 저장하는 소스를 짰다.
실행은 되는데 오류 메시지가 나오면서 자꾸 멈춰서 몇시간을 헤맸다...
결국 vector에 max_size()가 있다는걸 알아내고 소스를 수정했더니 제대로 된다!

신고

#include<iostream>
#include<algorithm>
using namespace std;


// 점 2개와 가중치를 Pair Class로 만들고,
// STL의 sort함수를 이용하기 위해
// 비교연산자를 오버로딩함.
class Pair
{
public:
	int a, b, weight;
	bool operator>(const Pair& pair) const
	{
		if(weight > pair.weight)
			return true;
		return false;
	}
	bool operator<(const Pair& pair) const
	{
		if(weight < pair.weight)
			return true;
		return false;
	}
};


// Cycle 생성 여부를 체크하기 위해 Disjoint Set을 이용.
// 연결되어 있는 정점들 사이에서 가장 작은 정점 번호를,
// 연결되어 있는 모든 정점들을 인덱스로 갖는 v배열에 대입
// 예를 들어 3,7,9번 정점이 연결되어 있으면
// v[3], v[7], v[9]는 모두 3을 값으로 갖게됨.
void makeSet(Pair* pair, int* v, const int& numV)
{
	int maxVal = max(v[pair->a], v[pair->b]);
	int minVal = min(v[pair->a], v[pair->b]);
	
	for(int i=1 ; i<=numV ; i++)
		if(v[i] == maxVal)
			v[i] = minVal;
}


int main(void)
{
	int numV, numE, loopLimit, min, max,
		cntE, slimness, v[101];
	bool isConnected;
	Pair pair[4950];

	while(true)
	{
		cin >> numV >> numE;

		// 종료조건
		if(numV==0 && numE==0)
			break;

		// Disjoint Set이용하기 위해,
		// 입력받은 정점개수 만큼 v배열 초기화
		// (인덱스 0은 이용하지 않음.)
		for(int j=1 ; j<=numV ; j++)
			v[j] = j;		

		// 입력 받으면서 초기에 입력받는 Pair들로
		// 스패닝 트리가 생성될 수 있는지 여부를
		// 검사하기 위해 makeSet함수를 호출
		for(int j=0 ; j<numE ; j++)
		{
			cin >> pair[j].a >> pair[j].b >> pair[j].weight;
			makeSet(&pair[j], v, numV);
		}
		
		isConnected = true;

		// 스패닝 트리가 생성될 수 있는지 여부를 체크.
		// 입력받은 Pair들이 모두 연결되어 있어야 하기 때문에
		// v배열의 값이 모두 1인 상태여야 함.
		for(int j=1 ; j<numV ; j++)
		{
			if(v[j]!=v[j+1])
			{
				isConnected = false;
				break;
			}
		}
		
		// 연결되어있지 않거나(!isConnected)
		// edge의 수가 vertex-1보다 작은 경우
		// 스패닝트리를 만들 수 없기 때문에 -1출력 후 continue;
		if(numE < numV-1 || !isConnected)
		{
			cout<< -1 <<endl;
			continue;
		}
		
		// 입력된 pair들을 가중치(w)를 기준으로 정렬
		// (오버로딩한 비교연산자 쓰임)
		sort(pair, pair+numE);

		// numE-(numV-1) + 1
		loopLimit = numE-numV+2;

		// 정렬된 pair들로 스패닝트리를 생성하면서
		// 최소 slimness를 찾음.
		for(int i=0 ; i<loopLimit ; i++)
		{
			// 선택된 edge의 개수를 count
			cntE = 1;
			// i번째 pair는 무조건 포함한 상태로
			// 스패닝트리를 찾아나가기 때문에
			// cntE를 1로 초기화하고,
			// i번째 weight를 min과 max로 설정
			min = max = pair[i].weight;

			// v 배열을 다시 초기화
			for(int j=1 ; j<=numV ; j++)
				v[j] = j;
			
			// i번째 pair로 makeSet함수 호출
			// (스패닝트리에 포함되는 모든 pair는
			// makeSet을 이용하여 Disjoint Set을 만듬)
			makeSet(&pair[i], v, numV);
			
			// i+1부터 스패닝트리가 완성되거나(cntE<numV-1)
			// 모든 edge를 검사(j<numE)할 때까지 루프 돔
			for(int j=i+1 ; j<numE && cntE<numV-1 ; j++)
			{
				// pair의 두 정점이 이미 연결되어 있지 않다면
				// (추가하여도 cycle을 만들지 않는다면)
				// weight를 검사하여 min, max값을 조정하고,
				// makeSet함수를 호출하여 Disjoint Set에 포함시킴.
				if(v[pair[j].a] != v[pair[j].b])
				{
					if(min > pair[j].weight)
						min = pair[j].weight;
					else if(max < pair[j].weight)
						max = pair[j].weight;

					makeSet(&pair[j], v, numV);
					cntE++;
				}
			}

			// 처음 생성된(첫번째 루프) 스패닝트리의
			// slimness는 바로 변수에 저장하고,
			// 그 다음부터 생성되는 스패닝트리의 slimness는
			// 이전의 slimness와 비교하여 작으면 저장하게 한다.
			// cntE == numV-1는 스패닝트리가 맞는지 검사하는 조건.
			if(i==0)
				slimness = max-min;
			else if(cntE == numV-1 && max-min < slimness)
				slimness = max-min;
		}

		// 최소 slimness 출력
		cout<< slimness <<endl;
	}

	return 0;
}

신고