글 읽기 - 메모리초과

hansx2079 5년 전 0

소스코드에서 두개 그냥 단순히 변수명만 바꿨을뿐인데

틀렸습니다에서 메모리초과로 바뀌네요 변수명 같은것도 관련이 있는건가요 ?

또 그 이문제를 제출할때 계속 틀리길래 맞은사람의 소스코드를 보면서 계속 수정해가면서 결국 배낀수준정도로 변수명 빼고 완전히 구조가 일치하는데

왜 제코드는 틀리는것일까요

첫번째 소스코드가 정답이 맞은분의 코드이구요

2번째가 메모리초과 뜬 문제

3번째가 틀린문제입니다.

//////////////////////맞은 분의 코드 
/////이게 정답인 코드
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct Data {
	int y, x;
};


int n, k,m;
int _map[2005][2005];
int chk[2005][2005];
int p[100005];
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };

int _find(int x) {
	if (p[x] == x)return x;
	return p[x] = _find(p[x]);
}
bool _union(int x, int y) {
	x = _find(x);
	y = _find(y);
	if (x == y)return false;
	p[x] = y;
	return true;
}
bool Range(int y, int x) {
	if (y<1 || x<1 || y>n || x>n)return false;
	return true;
}
queue<Data>q;
int main() {
	for (int i = 0; i < 100001; i++)p[i] = i;

	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		_map[a][b] = i+1;
		q.push({ a,b });

		for (int j = 0; j < 4; j++) {
			int ny = a + dy[j];
			int nx = b + dx[j];
			if (Range(ny, nx) && _map[ny][nx]!=0){
				if (_union(_map[ny][nx], _map[a][b])) {
					m++;
				}
			}
		}
	}
	int t = 0;
	
	while (1) {
		if (m == k - 1)break;
		t++;
		int _size = q.size();
		for (int s = 0; s < _size; s++) {
			Data now = q.front();	q.pop();


			for (int i = 0; i < 4; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];

				if (Range(ny, nx)) {
					if (_map[ny][nx] == 0) {
						_map[ny][nx] = _map[now.y][now.x];

						for (int j = 0; j < 4; j++) {
							int nny = ny + dy[j];
							int nnx = nx + dx[j];
							if (Range(nny, nnx) && _map[ny][nx] != _map[nny][nnx] && _map[nny][nnx] != 0) {
								if (_union(_map[ny][nx], _map[nny][nnx])) {
									m++;
								}
							}
						}
						q.push({ ny,nx });
					}
				}
			}
		}
	}
	cout << t << endl;
	return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////




#include<iostream>
#include<queue>
using namespace std;
struct Data{
	int y, x;
};

int n, k, m;
int _map[2005][2005];
int Par[100005];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int find(int x){
	if (Par[x] == x) return x;
	return Par[x] = find(Par[x]);
}
bool unions(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y)return false;
	Par[x] = y;
	return true;
}
bool Range(int x, int y){
	if (x < 1 || y < 1 || x > n || y > n) return false;
	return true;
}
queue<Data> q;
int main(){
	for (int i = 0; i < 100001; i++)Par[i] = i;
	cin >> n >> k;
	for (int i = 0; i < k; i++){//초기화
		int x, y;
		cin >> x >> y;
		_map[x][y] = i + 1;
		q.push({ x,y });

		for (int o = 0; o < 4; o++){//처음 문명 합병
			int tx = x + dx[o];
			int ty = y + dy[o];
			if (Range(tx, ty) && _map[tx][ty] != 0){
				if (unions(_map[tx][ty], _map[x][y])) {
					m++;
				}
			}
		}
	}
	int c = 0;

	while (true) {
		if (m == k - 1)break; // 문명이 하나일때 탈출 
		c++;
		int qs = q.size();
		for (int i = 0; i < qs; i++) {
			Data qq = q.front(); q.pop();


			for (int o = 0; o < 4; o++) {
				int tx = qq.x + dx[o];
				int ty = qq.y + dy[o];

				if (Range(tx, tx)) {
					if (_map[tx][ty] == 0) {
						_map[tx][ty] = _map[qq.x][qq.y];

						for (int j = 0; j < 4; j++) {
							int ttx = tx + dx[j];
							int tty = ty + dy[j];
							if (Range(ttx, tty) && _map[tx][ty] != _map[ttx][tty] &&  _map[ttx][tty] != 0) {
								if (unions(_map[tx][ty], _map[ttx][tty])) {
									m++;
								}
							}
						}
						q.push({ tx,ty });
					}
				}
			}
		}
	}
	cout << c << endl;
	return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
#include<iostream>
#include<queue>
using namespace std;
struct Vec{
	int x, y;
};

int N, K, M;
int World[2005][2005];
int Par[100005];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int find(int x){
	if (Par[x] == x) return x;
	return Par[x] = find(Par[x]);
}
bool unions(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y)return false;
	Par[x] = y;
	return true;
}
bool Range(int x, int y){
	if (x < 1 || y < 1 || x > N || y > N) return false;
	return true;
}
queue<Vec> q;
int main(){
	for (int i = 0; i < 100001; i++)Par[i] = i;
	cin >> N >> K;
	for (int i = 0; i < K; i++){//초기화
		int x, y;
		cin >> x >> y;
		World[x][y] = i + 1;
		q.push({ x,y });

		for (int o = 0; o < 4; o++){//처음 문명 합병
			int tx = x + dx[o];
			int ty = y + dy[o];
			if (Range(tx, ty) && World[tx][ty] != 0){
				if (unions(World[tx][ty], World[x][y])) {
					M++;
				}
			}
		}
	}
	int c = 0;

	while (true) {
		if (M == K - 1)break; // 문명이 하나일때 탈출 
		c++;
		int qs = q.size();
		for (int i = 0; i < qs; i++) {
			Vec qq = q.front(); q.pop();


			for (int o = 0; o < 4; o++) {
				int tx = qq.x + dx[o];
				int ty = qq.y + dy[o];

				if (Range(tx, tx)) {
					if (World[tx][ty] == 0) {
						World[tx][ty] = World[qq.x][qq.y];

						for (int j = 0; j < 4; j++) {
							int ttx = tx + dx[j];
							int tty = ty + dy[j];
							if (Range(ttx, tty) && World[tx][ty] != World[ttx][tty] &&  World[ttx][tty] != 0) {
								if (unions(World[tx][ty], World[ttx][tty])) {
									M++;
								}
							}
						}
						q.push({ tx,ty });
					}
				}
			}
		}
	}
	cout << c << endl;
	return 0;
}

djm03178 5년 전 0

맨 위의 구조체에서 x, y를 선언하는 순서가 다릅니다.

그 때문에 q.push({ tx, ty }); 는 서로 반대로 값을 넣게 됩니다.

hansx2079 5년 전 0

제 소스코드가 계속 틀리다고하길래 바꿨는데 실수를했네요 그러면 메모리 초과는 해결한 상태입니다.

그런데 구조체 순서를 바꾸고 한거를 다시 제출하니까 구조가 완전히 똑같은데도 제껀 틀렸다고 나오네요

djm03178 5년 전 0

2번째가 틀리는 이유는 구조체에서의 순서는 y, x이므로 q.push({ ty, tx }); 여야 하는데 반대로 해서이고, 3번째가 메모리 초과인 이유는 247번째 줄이 Range(tx, ty)여야 하는데 Range(tx, tx) 라고 썼기 때문입니다.

djm03178 5년 전 0

2번째 코드에도 Range(tx, tx) 라고 되어 있습니다.

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

문제

문제

출처

ICPC

메모리초과

hansx2079 5년 전 0

djm03178 5년 전 0

hansx2079 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말