[C++] 백준 3197 백조의 호수

 
#include <iostream> 
#include <vector> 
#include <string>
#include <queue> 
 
int DirX[4] = { 1,-1,0,0 };
int DirY[4] = { 0,0,1,-1 };
bool visit[1501][1501] = {};
int R = 0;
int C = 0;
std::string graph[1501];
 
int main() 
{ 
	std::cin >> R >> C;
	std::vector<std::pair<int, int>> vec = {}; 
	std::queue<std::pair<int, int>> waterQue = {}; 
 
	for (int i = 0; i < R; ++i)
	{ 
		std::cin >> graph[i]; 
 
		for (int j = 0; j < C; ++j) 
		{ 
			if (graph[i][j] == 'L') 
				vec.push_back({ i, j }); 
 
			// 물 위치 입력
			if (graph[i][j] == '.' || graph[i][j] == 'L') 
				waterQue.push({ i, j }); 
		} 
	} 
 
	std::queue<std::pair<int, int>> que = {}; 
 
	que.push(vec[0]); 
	visit[vec[0].first][vec[0].second] = true; 
 
	int iCount = 0;
 
	while (true) 
	{
		std::queue<std::pair<int, int>> nextQue = {}; 
		bool bFind = false; 
 
		while (!que.empty()) 
		{
			int iX = que.front().first; 
			int iY = que.front().second; 
			que.pop(); 
 
			if (iX == vec[1].first && iY == vec[1].second) 
			{ 
				// 찾을 시 끝
				bFind = true; 
				break; 
			} 
 
			for (int i = 0; i < 4; ++i) 
			{
				int iNextX = iX + DirX[i]; 
				int iNextY = iY + DirY[i]; 
 
				if (iNextX < 0 || iNextX >= R || iNextY < 0 || iNextY >= C)
					continue;
 
				if (visit[iNextX][iNextY])
					continue; 
 
				visit[iNextX][iNextY] = true; 
 
				// 언 곳이라면
				if (graph[iNextX][iNextY] == 'X') 
				{ 
					// 다음 큐로 입력
					nextQue.push({ iNextX, iNextY }); 
					continue; 
				} 
 
				// 얼지 않았다면 다시 확인
				que.push({ iNextX, iNextY }); 
			} 
		} 
 
		if (bFind) 
			break; 
 
		// 다음 반복 시 때 que에 넣어놓기
		que = nextQue; 
 
		int iSize = waterQue.size(); 
 
		// 입력된만큼만 녹인다.
		while (iSize--) 
		{ 
			int iX = waterQue.front().first; 
			int iY = waterQue.front().second; 
			waterQue.pop(); 
 
			for (int i = 0; i < 4; ++i) 
			{ 
				int iNextX = iX + DirX[i]; 
				int iNextY = iY + DirY[i]; 
 
				if (iNextX < 0 || iNextX >= R || iNextY < 0 || iNextY >= C) 
					continue;
 
				// 다음에 녹을 곳을 입력해놓는다.
				if (graph[iNextX][iNextY] == 'X') 
				{ 
					graph[iNextX][iNextY] = '.'; 
 
					waterQue.push({ iNextX, iNextY }); 
				} 
			} 
		} 
 
		// 다음 반복 횟수
		++iCount; 
	} 
 
	std::cout << iCount;
 
	return 0; 
}
 

처음에는 시간 초과... 그 후로는 메모리 초과가 나왔는데

시간 초과보다는 메모리 초과가 더 많이 나왔다.

que를 더 많이 사용하고 검색 범위가 넓었다.

했던 곳을 다시 검색하지 않고 그 범위에서 더 넓어져갔어야 했다.

이런 방식으로도 que를 사용할 수 있구나 생각된다.