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

winnyiee 5년 전 0

메모리 초과가 나옵니다.

코드는 보시다싶이 기본적인 bfs 코드입니다. 어느 부분에서 메모리 초과가 발생하는 것일까요?

#include <iostream>
#include <queue>

using namespace std;
int visit[51][51] ;
int arr[51][51] ;
void bfs(int y, int x);
int M, N, K;
int main()
{
	int T;
	

	cin >> T;

	for (int z = 0; z < T; z++) {
		
		cin >> M >> N >> K;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visit[i][j] = 0;
				arr[i][j] = 0;
			}
			
		}
		for (int i = 0; i < K; i++) {
			int x, y;

			cin >> x;
			cin >> y;
			arr[y][x] = 1;
		}
		
		int val = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 1 && visit[i][j] == 0) {

					bfs(i, j);
					val += 1;

				}
			}
		}
		cout << val<<endl;
	}
}

void bfs(int y, int x) {
	queue<pair<int,int>> q;
	q.push({ y, x });
	visit[y][x] = 1;

	while (!q.empty()) {
		
		int tempy = q.front().first;
		int tempx = q.front().second;
		q.pop();

		
		
		visit[tempy][tempx] = 1;

		if (tempy+1<N &&arr[tempy + 1][tempx] == 1 && visit[tempy + 1][tempx] == 0) {
				q.push({ tempy + 1,tempx });
			}
		if (tempy - 1>=0&&arr[tempy - 1][tempx] == 1 && visit[tempy - 1][tempx] == 0) {
				q.push({ tempy - 1,tempx });
			}
		if (tempx + 1<M&&arr[tempy][tempx+1] == 1 && visit[tempy][tempx+1] == 0) {
				q.push({ tempy ,tempx+1 });
			}
		if (tempx - 1>=0&&arr[tempy][tempx-1] == 1 && visit[tempy][tempx-1] == 0) {
			q.push({ tempy ,tempx-1 });
			}
		
	}
	

}

hyunynim 5년 전 2

큐에 넣을때 방문확인을 체크하는것이 좋을것 같네요

63번째 줄을 각 if문 안으로 넣어보는게 어떨까요

winnyiee 5년 전 0

그렇게하니 되네요!

그런데 이해는 잘 안가네요 ㅠㅠ

큐에 넣을때 방문 확인을 하는 것과 큐에서 뺄때 하는 것이 차이가 많이 나나요..?

hyunynim 5년 전 2

큐에서 뺄때 방문확인을 하시면 중복된 정보가 큐에 들어가게 되서 메모리초과가 나는걸로 보입니다!

winnyiee 5년 전 0

감사합니다정말!!

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

문제

문제

출처

ICPC

1012 유기농 배추 메모리 초과

winnyiee 5년 전 0

hyunynim 5년 전 2

winnyiee 5년 전 0

hyunynim 5년 전 2

winnyiee 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말