글 읽기 - 16236 아기 상어, 메모리초과 발생 원인 파악 문의 드립니다.

keh2970 4년 전 0

16236 아기 상어, 메모리초과 발생 원인 파악 문의 드립니다.

어느 부분에서 메모리초과가 발생하는지 모르겠네요.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N;
int iMap[20][20];

struct Fish
{
	int nSize;
	int nOld;
	int iPos;
	int jPos;
	int nTime;
};

Fish babyShark;

bool bVisited[20][20];
int iDir[4][2] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } };

void game()
{
	queue<pair<int,int>> q;
	bool bFind = false;
	int iFind = 0, jFind = 0;
	int iCur, jCur, iNext, jNext;
	int nTime = 0;

	q.push(pair<int,int>(babyShark.iPos, babyShark.jPos));

	while (!q.empty())
	{
		iFind = 21;
		jFind = 21;

		int iQsize = q.size();

		while (iQsize--)
		{
			iCur = q.front().first;
			jCur = q.front().second;
			q.pop();
			bVisited[iCur][jCur] = true;

			if (iMap[iCur][jCur] && iMap[iCur][jCur] < babyShark.nSize)
			{
				if (iCur < iFind)
				{
					bFind = true;
					iFind = iCur;
					jFind = jCur;
				}
				else if (iCur == iFind)
				{
					if (jCur < jFind)
					{
						bFind = true;
						iFind = iCur;
						jFind = jCur;
					}
				}
			}

			if (bFind)
				continue;

			for (int i = 0; i < 4; i++)
			{
				iNext = iCur + iDir[i][0];
				jNext = jCur + iDir[i][1];

				if (iNext < 0 || jNext < 0 || iNext >= N || jNext >= N)
					continue;
				if (bVisited[iNext][jNext])
					continue;
				if (iMap[iNext][jNext] > babyShark.nSize)
					continue;

				q.push(pair<int,int>(iNext,jNext));
			}
		}

		if (bFind)
		{
			bFind = false;

			babyShark.nOld++;
			if (babyShark.nOld == babyShark.nSize)
			{
				babyShark.nSize++;
				babyShark.nOld = 0;
			}

			babyShark.iPos = iFind;
			babyShark.jPos = jFind;
			iMap[iFind][jFind] = 0;

			babyShark.nTime += nTime;
			nTime = 0;

			while (!q.empty())
				q.pop();
			q.push(pair<int, int>(babyShark.iPos, babyShark.jPos));

			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					bVisited[i][j] = false;
		}
		else
			nTime++;
	}
}

int main()
{
	cin >> N;

	babyShark.nSize = 2;
	babyShark.nOld = 0;
	babyShark.nTime = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			bVisited[i][j] = false;
			cin >> iMap[i][j];
			if (iMap[i][j] == 9)
			{
				iMap[i][j] = 0;
				babyShark.iPos = i;
				babyShark.jPos = j;
			}
		}
	}

	game();

	cout << babyShark.nTime << endl;

    return 0;
}

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

문제

문제

출처

ICPC

16236 아기 상어, 메모리초과 발생 원인 파악 문의 드립니다.

keh2970 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말