글 읽기 - 메모리 초과는 왜 나는 건가요?

math_rabbit_1028 4년 전 0

통나무들 사이에 이동할 수 있는지 여부를 판단하여 코드를 작성하였습니다.

참고적으로 A와 B 사이에 C가 존재해 A와 B 사이를 이동할 수 없어도 C를 통하여 이동할 수 있기 때문에 상관이 없다고 생각하고 코드를 작성하였습니다.

그런데 이 코드에서 메모리 초과가 납니다. 왜 그런지 알려주세요.

//17619 - 개구리 점프
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Log {
	int num;
	int x1;
	int x2;
};

int n, q;
vector<Log> loc; 
vector<int> root;

int Find(int v) {
	if (v == root[v]) return v;
	else return root[v] = Find(root[v]);
}

void Union(int v1, int v2) {
	int x = root[v1], y = root[v2];
	if (x != y) root[x] = y;
}

bool compare(Log a, Log b) {
	return a.x1 < b.x1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	root.push_back(0);
	for (int i = 1; i <= n; i++) {
		int temp, a, b;
		Log c;
		cin >> a >> b >> temp;
		c.num = i;
		c.x1 = a;
		c.x2 = b;
		loc.push_back(c);
		root.push_back(i);
	}
	sort(loc.begin(), loc.end(), compare);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (loc[i].x2 >= loc[j].x1) {
				Union(loc[i].num, loc[j].num);
			}
			else break;
		}
	}
	for (int i = 1; i <= q; i++) {
		int a, b;
		cin >> a >> b;
		if (Find(a) == Find(b)) cout << "1\n";
		else cout << "0\n";
	}
	return 0;
}

kcan1416 4년 전 1

22번줄을 int x = Find(v1), y = Find(v2); 로 바꿔주세요

그리고 이 문제는 union-find를 사용하지 않고 반복문 하나로도 푸는게 가능합니다

math_rabbit_1028 4년 전 0

실수가 있었네요

고쳐주셔서 감사합니다.

minjoonist 3년 전 0

@kcan1416 O(n) 으로 이 문제를 푸는게 가능한가요?

kcan1416 3년 전 0

정렬이 필요해서 O(NlogN)입니다 정렬 후 스위핑하면 됩니다

지금보니까 제가 오해가 생길 수 있도록 적어두었네요..

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

문제

문제

출처

ICPC

메모리 초과는 왜 나는 건가요?

math_rabbit_1028 4년 전 0

kcan1416 4년 전 1

math_rabbit_1028 4년 전 0

minjoonist 3년 전 0

kcan1416 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말