글 읽기 - C++ 메모리초과 질문드립니다.

av3rs1on 2년 전 0

다음 순으로 구현했습니다

1. 입력을 받으면서 1인 지점을 저장해줍니다.

2. bfs를 돌면서 대륙간 번호를 지정해주어 저장합니다. - divide_map

3. 1에서 입력받은 x, y 좌표 값을 검사하여 4면 중 한면이라도 0이 있다면 bfs를 돌려줍니다.

메모리 초과가 나는데 어떤 부분에서 문제가 있는건지 모르겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int n;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int _value = 987654321;

int map[101][101];
int divide_map[101][101];
int _tmp_map[101][101];
int _land = 0;

int _find_briedge(int x, int y) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			_tmp_map[i][j] = divide_map[i][j];
		}
	}
	priority_queue<tuple<int, int, int>> q;
	int _start_land = divide_map[x][y];
	q.push(make_tuple(0, x, y));

	while (!q.empty()) {
		auto _cnt = -get<0>(q.top());
		auto x = get<1>(q.top());
		auto y = get<2>(q.top());

		if (divide_map[x][y] != _start_land && divide_map[x][y] != 0) {
			return _cnt-1;
			break;
		}

		_tmp_map[x][y] = _start_land;
		q.pop();

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

			//경계값이면 취소
			if (nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;
			if (_tmp_map[nx][ny] == _start_land)
				continue;
			q.push(make_tuple(-_cnt - 1, nx, ny));
		}
	}
	return 987654321;
}

void _divide_bfs(int x, int y) {
	queue<pair<int, int>> q;
	divide_map[x][y] = ++_land;
	q.push({ x,y });

	while (!q.empty()) {
		auto x = q.front().first;
		auto y = q.front().second;
		divide_map[x][y] = _land;
		q.pop();

		for (int i = 0; i < 4; i++) {
			auto nx = x + dx[i];
			auto ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;
			if (map[nx][ny] == 0)
				continue;
			if (divide_map[nx][ny] == _land || divide_map[nx][ny] != 0)
				continue;
			divide_map[nx][ny] = _land;
			q.push({ nx, ny });
		}
	}
}

int main(void) {
	vector<pair<int, int>> v;
	cin >> n;
	//map initialize to -1
	for (int i = 0; i < n+1; i++) {
		for (int j = 0; j < n+1; j++) {
			map[i][j] = -1;
			divide_map[i][j] = 0;
		}
	}

	//input
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				v.push_back({ i, j });
		}
	}
	
	//land divide		
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && divide_map[i][j] == 0) {
				_divide_bfs(i, j);
			}
		}
	}
	//find border & execute bfs
	for(int a = 0 ; a < v.size() ; a++) {
		auto i = v[a].first;
		auto j = v[a].second;

		for (int k = 0; k < 4; k++) {
			int a = dx[k];
			int b = dy[k];
			if (i + a < 0 || i + a >= n || j + b < 0 || j + b >= n)
				continue;
			if (map[i + a][j + b] == 0 && divide_map[i][j] != 0) {
				_value = min(_value, _find_briedge(i, j));
				break;
			}
		}
	}
	cout << _value;
}

dldyddlwl 2년 전 0

아래에 있습니다.

// ... 코드 중략


int _find_briedge(int x, int y) {
    // ... 코드 중략
	while (!q.empty()) {

		for (int i = 0; i < 4; i++) {
            // 방문처리 및 방문확인 과정을 통한 메모리 절약
			q.push(make_tuple(-_cnt - 1, nx, ny));    // 방문처리가 없게 된다면, 같은 곳을 또 방문하게 되어   
		}                                            // 메모리초과가 뜹니다.
        
        
        
      //
        
        
        
                    if (_tmp_map[nx][ny] == _start_land)
				        continue;
                    // 현재 과정
                    // nx ny 좌표가 시작대륙이 아니라면, 무조건 push가 일어남
                    // 그렇게 되면 바다에서 너무 많은 push가 일어남.
        




    // ... 코드 중략




	for(int a = 0 ; a < v.size() ; a++) {
		auto i = v[a].first;
		auto j = v[a].second;

		for (int k = 0; k < 4; k++) {
			int a = dx[k];
			int b = dy[k];
			if (i + a < 0 || i + a >= n || j + b < 0 || j + b >= n)
				continue;
			if (map[i + a][j + b] == 0 && divide_map[i][j] != 0) {
                // 매번 방문 배열의 초기화의 필요성!!
                // 매번의 find_bridge함수는 같은 방문값을 공유해서는 안됨, 완전 새로운 시작이므로 초기화 필요!
				_value = min(_value, _find_briedge(i, j));
				break;
			}
		}
	}
	cout << _value;
}

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

문제

문제

출처

ICPC

C++ 메모리초과 질문드립니다.

av3rs1on 2년 전 0

dldyddlwl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말