글 읽기 - 메모리 초과 어느부분을 처리해야도리까요

dt43111 7년 전 0

안녕하세요 해당 문제 메모리초과되서 여쭤봅니다

각 백조를 L1, L2라고 했을때

L1이 갈수있는부분을 모두 채우고, L2도 갈수있는부분을 모두채웁니다

채울때 벽을만나면 벽부분을 또 다른 큐 1,2에 넣으면서요

그후 와일문을돌며 큐1에서 도 뻗어가는 1을만나는부분을 큐에넣습니다

큐 2도 위처럼 합니다

그 와중에 2가있으면 or 1이있으면 cnt출력후 종료되게 만들었습니다

전 소스에서 메모리초과가 떠서 다 지우고 고려를 하면서 짯는데도 해결이안되네요

답변부탁드리겠습니다

감사합니다

// 백조의 호수
// https://www.acmicpc.net/problem/3197



#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#include<functional>
#include<algorithm> 
using namespace std;

int map[1506][1506];
int vis[1506][1506]; 

int w, h; 

int dY[] = { 0, 0, 1, -1 };
int dX[] = { 1, -1, 0, 0 };

int sttY, sttX, endY, endX;

queue<pair<int, int>> q1;
queue<pair<int, int>> q2;
queue<pair<int, int>> q1set; // 처음에 채우면서 q1에 얼음테두리넣는큐
queue<pair<int, int>> q2set; // " q2

void coutpr()
{
	for (int i = 0; i <= h+1; i++)
	{

		for (int j = 0; j <= w+1; j++)
		{
			cout << vis[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
  

int main()
{
//	freopen("input.txt", "r", stdin);

	scanf("%d %d", &h, &w);

	string str;

	for (int i = 1; i <= h; i++)
	{
		cin >> str;

		for (int j = 1; j <= w; j++)
		{
			if (str.at(j - 1) == 'X')
			{
				map[i][j] = 1;
			}
			else if (str.at(j - 1) == '.')
			{
				map[i][j] = 0;
			}
			else if (str.at(j - 1) == 'L') // 백조 1, 2
			{
				if (q1set.empty())
				{
 					q1set.push({ i, j });
					vis[i][j] = 1;
				}
				else
				{
					q2set.push({ i, j });
					vis[i][j] = 2;
				}
			}
		}
	}

    // 두리두리 테두리
	for (int i = 0; i <= h + 1; i++)
	{
		map[i][0] = map[i][w + 1] = -1;
	}

	for (int i = 0; i <= w + 1; i++)
	{
		map[0][i] = map[h + 1][i] = -1;
	}

    //처음 지점에서 갈수있는곳 채우기 + 처음지점에서 벽만났을때 다른 큐에 넣기
	while (!q1set.empty())
	{
		int curY = q1set.front().first;
		int curX = q1set.front().second;
		q1set.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = curY + dY[i];
			int nextX = curX + dX[i];

			if (vis[nextY][nextX] == 2)
			{
				cout << 0 << endl;
				return 0;
			}

			if (map[nextY][nextX] == 0 && vis[nextY][nextX] == 0)
			{
				vis[nextY][nextX] = 1;
				q1set.push({ nextY, nextX });
			}
			else if (map[nextY][nextX] == 1 && vis[nextY][nextX] == 0)
			{
				q1.push({ nextY, nextX });
			}

		}

	}
	  
    //처음 지점에서 갈수있는곳 채우기 + 처음지점에서 벽만났을때 다른 큐에 넣기
	while (!q2set.empty())
	{
		int curY = q2set.front().first;
		int curX = q2set.front().second;
		q2set.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = curY + dY[i];
			int nextX = curX + dX[i];
			 
			if (map[nextY][nextX] == 0 && vis[nextY][nextX] == 0)
			{
				vis[nextY][nextX] = 2;
				q2set.push({ nextY, nextX });
			}
			else if (map[nextY][nextX] == 1 && vis[nextY][nextX] == 0)
			{
				q2.push({ nextY, nextX });
			}

		}

	}
	 
	int dayCnt = 1;

	while (1)
	{

		int curY, curX;


		queue<pair<int, int>> forCpyQ1; 
		queue<pair<int, int>> forCpyQ2; 

        // q1확장하면서 맵에서 0이면 통과, 1이면 그부분 다른큐에 넣었다가 다시 q1에넣기 ( 반복)
		while (!q1.empty())
		{
			curY = q1.front().first;
			curX = q1.front().second;
			q1.pop();

			vis[curY][curX] = 1;

			for (int i = 0; i < 4; i++)
			{
				int nextY = curY + dY[i];
				int nextX = curX + dX[i];

				if (vis[nextY][nextX] == 2) // 도중 2를만나면 dayCnt출력
				{
					cout << dayCnt << endl;
					return 0;
				}

				if (map[nextY][nextX] == 0 && vis[nextY][nextX] == 0) // 맵이0일때 퍼지기
				{
					vis[nextY][nextX] = 1;
					q1.push({ nextY, nextX });
				}
				else if (map[nextY][nextX] == 1 && vis[nextY][nextX] == 0)// 맵이1일때 다른큐에넣어놓기 (추후옴김)
				{
					forCpyQ1.push({ nextY, nextX });
				}
			}
		}

		q1 = forCpyQ1;
		
		//coutpr();

        // q2확장하면서 맵에서 0이면 통과, 1이면 그부분 다른큐에 넣었다가 다시 q2에넣기 ( 반복)
		while (!q2.empty())
		{
			curY = q2.front().first;
			curX = q2.front().second;
			q2.pop();

			vis[curY][curX] = 2;

			for (int i = 0; i < 4; i++)
			{
				int nextY = curY + dY[i];
				int nextX = curX + dX[i];

				if (vis[nextY][nextX] == 1) // 도중 1을만나면 dayCnt출력
				{
					cout << dayCnt << endl;
					return 0;
				}

				if (map[nextY][nextX] == 0 && vis[nextY][nextX] == 0) // 맵이0일때 퍼지기
				{
					vis[nextY][nextX] = 2;
					q2.push({ nextY, nextX });
				}
				else if (map[nextY][nextX] == 2 && vis[nextY][nextX] == 0) // 맵이1일때 다른큐에넣어놓기 (추후옴김)
				{
					forCpyQ2.push({ nextY, nextX });
				}
			}
		}
		q2 = forCpyQ2;
		//coutpr();
		dayCnt++;
	}

}

sgchoi5 7년 전 1

이 문제는 답안도 있고, TC 도 있으니 잘 분석해보시기 바래요.. : )

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

메모리 초과 어느부분을 처리해야도리까요

dt43111 7년 전 0

sgchoi5 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말