글 읽기 - LCA 문제 런타임 에러로 질문 드립니다.

rlarlgns012 6년 전 0

일단 LCA 함수는 생각나는데로 짜서 이상하게 보이실 겁니다. ㅠㅠ

벡터 클래스를 하나 만들었구요 그안에 level 변수를 두어 해당 노드의 레벨을 담도록 하였습니다.

이차원 벡터로 트리를 표현하였고 한 노드에 연결된 다른 노드의 중에서 현재 노드보다 레벨이 낮은것은 부모뿐일것이다 라는 생각으로 함수를 만들어 돌렸습니다.

어디서 에러가 나는걸까요 ㅠㅠ

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

template <typename T>
class vector {
public:
	int capacity, _size;
	T* arr;
	int level;

	vector() {
		capacity = 4;
		_size = 0;
		level = 0;
		arr = new T[capacity];
	}

	void resize(int n) {
		T* temp = new T[n];
		for (int i = 0; i < _size; i++) {
			temp[i] = arr[i];
		}
		delete arr;
		arr = temp;
	}

	void push_back(T data) {
		if (_size == capacity) {
			capacity *= 2;
			resize(capacity);
		}
		arr[_size++] = data;
	}

	int size() {
		return _size;
	}

	T &operator [] (int idx) {
		return arr[idx];
	}
};

vector<vector<int>> tree;
bool visited[100002] = { 0 };

void Swap(int &a, int &b) { int t = a; a = b; b = t; }
int LCA(int n1, int n2) {
	int n1_level = tree[n1].level;
	int n2_level = tree[n2].level;

	if (n1_level < n2_level) {
		Swap(n1, n2);
		Swap(n1_level, n2_level);
	}
	// level 맞추기
	while (n1_level != n2_level) {
		for (int i = 0; i < tree[n1].size(); i++) {
			int t = tree[n1][i];
			if (tree[t].level < n1_level) {
				n1_level = tree[t].level;
				n1 = t;
				break;
			}
		}
	}

	if (n1 == n2) return n1;

	// 공통 부모 찾을때 까지 같이 증가
	while (n1 != n2) {
		for (int i = 0; i < tree[n1].size(); i++) {
			int t = tree[n1][i];
			// 트리에서 현재 노드의 레벨보다 작은것은 부모만 존재
			if (tree[t].level < n1_level) {
				n1_level = tree[t].level;
				n1 = t;
				break;
			}
		}
		for (int i = 0; i < tree[n2].size(); i++) {
			int t = tree[n2][i];
			if (tree[t].level < n2_level) {
				n2_level = tree[t].level;
				n2 = t;
				break;
			}
		}
	}
	return n1;
}
// DFS돌면서 레벨 설정
void Level_cnt(int idx, int level) {
	tree[idx].level = level;

	for (int i = 0; i < tree[idx].size(); i++) {
		if (visited[tree[idx][i]] == false) {
			visited[tree[idx][i]] = true;
			Level_cnt(tree[idx][i], level + 1);
		}
	}
}

int main() {

	int N, M;
	scanf("%d", &N);

	tree.capacity = N + 1;
	tree.resize(N + 1);
	int n1, n2;
	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d", &n1, &n2);
		tree[n1].push_back(n2);
		tree[n2].push_back(n1);
	}

	visited[1] = true;
	Level_cnt(1, 1);

	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &n1, &n2);
		int result = LCA(n1, n2);
		printf("%d\n", result);
	}

	return 0;
}

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

문제

문제

출처

ICPC

LCA 문제 런타임 에러로 질문 드립니다.

rlarlgns012 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말