글 읽기 - c++ 메모리초과 도와주세요!

alswp450 2년 전 0

방식은 bfs 구현하는 함수를 하나만들고

1들을 0이라고 한번씩생각해서 모든 경우의 수를 v 벡터에 넣고 가장 작은것을 출력해줬습니다.

너무 많은 값을 큐에 넣어서 그런걸까요??

#include<iostream>
#include<string> 
#include<queue>
#include<tuple>
#include<vector>

using namespace std;


vector <int> v;
void bfs(int N, int M);
void Break(int N, int M);
char** arr;

int main() {
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	int N,M;
	cin >> N >> M;
	arr = new char* [N];
	for (int i = 0; i < N; i++) {
		arr[i] = new char[M];
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> arr[i][k];
		}
	}
	
	Break(N,M);
	
}


void bfs(int N,int M) {
	int dx[4] = { 1,-1,0,0};
	int dy[4] = { 0,0,1,-1 };

	bool** c;
	c = new bool* [N];
	for (int i = 0; i < N; i++) {
		c[i] = new bool[M];
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (arr[i][k] == '1') { 
				c[i][k] = false;
			}
			else {
				c[i][k] = true;
			}
		}
	}

	int count = 0;
	int distance = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {

			if (c[i][k] && arr[i][k] == '0') {
				count++;

				queue <tuple<int, int, int>> q;
				distance = 0;
				q.push(make_tuple(i, k, distance));
				c[i][k] = false;

				while (!q.empty()) {
					int x = get<0>(q.front());
					int y = get<1>(q.front());
					distance = get<2>(q.front());
					q.pop();

					if (x == N - 1 && y == M - 1 && count==1 && i==0 && k ==0) {
						v.push_back(distance);
						break;
					}

					distance++;
					for (int h = 0; h < 4; h++) {
						int tmp = x + dx[h];
						int tmp2 = y + dy[h];


						if (tmp2 < 0 || tmp < 0 || tmp >= N || tmp2 >= M) {
							continue;
						}

						if (c[tmp][tmp2]) {
							q.push(make_tuple(tmp, tmp2, distance));
							c[tmp][tmp2] = false;
						}

					}

				}
			}
		}
	}

}


void Break(int N,int M) {
	int sz = 0;
	queue <pair<int, int>> qq;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (arr[i][k] == '1') {
				sz++;
				qq.push(make_pair(i, k));
			}
		}
	}
	bfs(N, M); // 그냥도 한번 해봄.
	for (int i = 0; i < sz; i++) {
		int x = get<0>(qq.front());
		int y = get<1>(qq.front());
		qq.pop();
		arr[x][y] = '0';
		bfs(N, M);
		arr[x][y] = '1';
	}

	if (v.empty()) {
		cout << -1;
	}
	else {
		int min = v[0];
		for (int i = 0; i < v.size(); i++) {
			if (min > v[i]) {
				min = v[i];
			}
		}
		cout << min+1;
	}
}

euphoric_n 2년 전 1

41-45번 줄 bool **c 에 최대 1000*1000개의 bool을 동적할당 하는 작업을 최대 1000*1000번 하고 계십니다.

동적할당을 했다면 delete[] c로 반환해주어야 합니다.

그와는 별개로 BFS를 최대 1000*1000번 실행하므로 무조건 시간초과입니다.

alswp450 2년 전 0

감사합니다!! 해결된거같아요!

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

문제

문제

출처

ICPC

c++ 메모리초과 도와주세요!

alswp450 2년 전 0

euphoric_n 2년 전 1

alswp450 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말