글 읽기 - 반례를 못찾겠습니다

skysujun 7년 전 0

bfs로 갈수 있는 노드에 방문하고, 나름 메모이제이션도 사용했다고 생각하는데 계속 틀렸다고 나옵니다. 혹시 문제가 뭔지 아시는 분 계신가요?

#include<stdio.h>

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };


int d[501][501];
int a[501][501];

	int data[1000000][3];
	int front, end;

	void push(int x, int y, int cnt)
	{
		data[end][0] = x;
		data[end][1] = y;
		data[end][2] = cnt;
		end += 1;
	}

	void pop()
	{
		front += 1;

	}

	bool empty()
	{
		if (front == end)
			return true;

		else
			return false;

	}

	int front_x()
	{
		return data[front][0];
	}

	int front_y()
	{
		return data[front][1];
	}

	int front_cnt()
	{
		return data[front][2];
	}




int main()
{

	int n;
	
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);


	//printf("\n");
	for (int i = 1; i <= n; i++)
	{
		front = 0;
		end = 0;

		for (int j = 1; j <= n; j++)
		{
			
				push(i, j, 1);
				int max_count = 0;

				while (!empty())
				{

					int x = front_x();
					int y = front_y();
					int ct = front_cnt();
					pop();

					if (ct > max_count)
						max_count = ct;

					for (int k = 0; k < 4; k++)
					{
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx >= 1 && ny >= 1 && n >= nx&&n >= ny)
						{
							if (a[nx][ny]>a[x][y])
							{
								if (d[nx][ny] > 0)
								{
									if (max_count < d[nx][ny] + ct)
									{
										max_count = d[nx][ny] + ct ;
									}
								}

								else
								{
									push(nx, ny, ct + 1);

								}

							}

						}
					}



				

			}

				if (d[i][j] < max_count)
					d[i][j] = max_count;

		}
	}


	//for (int i = 1; i <= n; i++)
	//{
	//	for (int j = 1; j <= n; j++)
	//	{
	//		printf("%d ", d[i][j]);
	//	}

	//	printf("\n");
	//}

	int result = 0;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (result < d[i][j])
			{

				result = d[i][j];
			}

		}

	printf("%d\n", result);
}

portableangel 7년 전 2

로직 상의 문제는 없어 보이나, 두 가지 문제점이 있습니다.

첫 번째는 queue의 크기가 부족합니다. 배열은 25만칸이지만,

예를 들어

1 4

2 3

과 같은 2*2 보드에서, 1행 2열의 4는 (1,1)->(2,1)->(2,2)->(1,2)에서 한 번, (1,1)->(1,2)에서 한 번 총 2번 푸시됩니다.

이렇게 되면 (2,1)에서 갈 수 있는 모든 칸은 두 번씩 방문되겠네요.

이 과정이 여러 번 중첩해서 쌓이면 100만 칸을 넘어갈 수 있습니다.

방문 체크를 통해 이 부분을 개선할 경우엔 두 번째 문제점이 있습니다.

현재 코드는 사실 DP가 아닙니다. 중복 계산되는 문제를 여러 번 중복 계산하는 것을 허용하고 있기 때문입니다.

N*N개의 칸에 대해 BFS를 실행하게 되니 시간복잡도는 O(N^4)이 되고, 만일 충분히 악의적인 입력이 있다면 시간 초과가 나겠네요.

이 문제는 (r,c)에서 시작하는 최대 경로 길이를 이용하는 O(N^2) DP 풀이가 존재합니다. 한번 다시 설계해보세요.

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