3-K 시간초과 질문드립니다.

작성한 질문수 35

0

안녕하세요 가인님 ㅎㅎ

로직상은 문제될게 없습니다.

다만, 이 문제는 시간이 타이트한 문제고 그래서 "불필요한 로직이 하나라도" 있으면 안됩니다.

지금 보시면...

	while (true)
	{
		fill(&visited[0][0], &visited[0][0] + 1501 * 1501, 0);

		Swan();
		if (Check() == false)
		{

이렇게 visited를 계속해서 초기화하고 swan을 하고 있습니다.

swan은..

void Swan()
{
	for (int y = 1; y <= R; y++)
		for (int x = 1; x <= C; x++)
			if (adj[y][x] == 'L')
			{
				q.push({ y,x });
				visited[y][x] = 1;

2중for문으로 L을 찾아서 push를 하는 것이구요. (육지를 찾는 것이죠.)

이거를 얼음을 녹이고 그 녹인 시점을 기준으로 하게 되면 for문이 필요 없습니다.

또한, ICE() 같은 경우도 비슷합니다. 매번 초기화 하고 ice를 작동시키는데요.

		if (Check() == false)
		{
			// 초기화
			fill(&visited[0][0], &visited[0][0] + 1501 * 1501, 0);
			while (q.size())
				q.pop();

			// 얼음 녹이기
			ICE();
			cnt++;

void ICE()
{
	// 얼음과 물 맞닿아있는 곳
	for (int y = 1; y <= R; y++)
		for (int x = 1; x <= C; x++)
			if (adj[y][x] == '.' || adj[y][x] == 'L')
			{
				for (int i = 0; i < 4; i++)

똑같이 2중for문을 쓰고 있습니다.

이렇게 생각하시면 될 것 같습니다.

갈색 원처럼 하나씩 탐색하면 되는 것을 가인님의 코드는 빨간색원처럼 모든 정점을 탐색해서 빨간색체크. 그리고 나서 -> 보라색 원처럼 모든 정점을 탐색해서 보라색체크 하는 코드라고 보시면 됩니다.

이부분이 걸려서 시간초과가 뜨는 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.