글 읽기 - 런타임 에러(bad alloc)발생 이유

vansoft 2년 전 0

왜 런타임 에러(bad alloc) 오류가 발생하는지 알고 싶습니다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define MAX 100000

int N; // 정점의 수
vector <int> Info[MAX]; // 간선
bool check[MAX]; // 방문 여부
int order[MAX]; // 방문 순서
int Parent[MAX]; // 부모 노드 확인 위함

void Input() {
	cin >> N; 

	for (int i = 0; i < N-1; i++)
	{
		int a, b;
		cin >> a >> b;

		Info[a].push_back(b);
		Info[b].push_back(a);
	}

	for (int i = 0; i < N; i++)
	{
		cin >> order[i];
	}
}

void BFS(int a) {
	queue <int> q;
	q.push(a);

	check[a] = true;
	int m = 1; // 큐의 크기

	for (int i = 0; i < N; i++)
		// 한 줄로 이어져 있으면, 최대 N번을 BFS를 진행해야 함. 
	{
		if (q.empty()) // BFS가 진행중임에도, 큐가 비게 된다면
		{
			cout << 0 << '\n';
			return;
		}

		int x = q.front();
		q.pop();

		if (x != order[i]) // 순서가 올바르지 않을 경우
		{
			cout << 0 << '\n';
			return;
		}

		int cnt = 0; // 이번에 큐에 넣어야 할 정점의 수
		for (int y : Info[x]) {
			if (check[y] == false)
			{
				Parent[y] = x; // y의 부모노드는 x이다.
				cnt += 1;
			}
		}

		for (int j = 0; j < cnt; j++)
		{
			if (m + j >= N || Parent[order[m + j]] != x) 
				// x와 연결되지 않은 정점이 큐에 들어가는 것은 올바르지 못함.
				// m+j번째로 들어가야 할 노드의 부모 노드가 x인가? 이를 확인해야함.
			{
				cout << 0 << '\n';
				return;
			}
			q.push(order[m + j]);
			// m+j번째로 들어가야 할 노드를 큐에 넣는다.
			check[order[m + j]] = true;
			// m+j번째로 들어가야 할 노드에 대해 탐색을 마쳤다고 변경해준다.
		}

		m += cnt; // 큐의 크기 + 탐색(이번 것과 연결된)한 노드 개수 => 그 다음번부터 탐색해야 하기 때문
	}

	cout << 1 << '\n';
	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	Input();
	BFS(1);// 시작지점은 무조건 1이다.

	return 0;
}

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

문제

문제

출처

ICPC

런타임 에러(bad alloc)발생 이유

vansoft 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말