글 읽기 - 1012 유기농배추 메모리초과

rkddustn96 4년 전 0

알고리즘상 문제는 없는듯 하고, 테스트케이스는 모두 맞는데 메모리초과가 뜹니다.

DFS로하면 쉽게 해결될 것 같기는 하지만 BFS쪽으로 마무리 하고싶어 질문 올려봅니다

메모리초과 이유 알려주시면 감사하겠습니다,

메모리초과 줄이는 방법같은 꿀팁도 같이 알려주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int map[50][50];
bool visit[50][50];

int M, N, K, ans;

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

queue<int> xq;
queue<int> yq;
queue<int> allans;

void BFS() {
	int xx, yy;
	
	while (xq.empty() != 1) {

		xx = xq.front(); yy = yq.front();

		visit[xx][yy] = true;

		xq.pop(); yq.pop();

		for (int i = 0; i < 4; i++) {
			if (map[xx + dx[i]][yy + dy[i]] == 1 && visit[xx + dx[i]][yy + dy[i]] == 0) {
				if (xx + dx[i] > -1 && xx + dx[i] < M && yy + dy[i]>-1 && yy + dy[i] < N) {
					xq.push(xx + dx[i]);
					yq.push(yy + dy[i]);
				}
			}
		}
	}

}

int main()
{
	int T = 0;
	cin >> T;

	while (T != 0) {
		
		memset(map, 0, sizeof(map));
		memset(visit, false, sizeof(visit));
		ans = 0;
		cin >> M >> N >> K;

		for (int i = 0; i < K; i++) {
			int xx = 0, yy = 0;
			cin >> xx >> yy;
			map[xx][yy] = 1;
		}

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
			{
				if (map[i][j] == 1 && visit[i][j] == 0)
				{
					xq.push(i); yq.push(j);
					BFS();
					ans++;
				}
			}
			
		allans.push(ans);
		T--;
	}
	
	while(allans.empty() != 1) {
		cout << allans.front() << endl;
		allans.pop();
	}
}

djm03178 4년 전 0

BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다.

rkddustn96 4년 전 0

댓글 감사합니다, 그냥 코드 한번 다 갈아버렸습니다ㅎㅎ

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

문제

문제

출처

ICPC

1012 유기농배추 메모리초과

rkddustn96 4년 전 0

djm03178 4년 전 0

rkddustn96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말