글 읽기 - 무엇이 잘못되엇을까요?..... 잘 모르겠습니다.

ejgrt 7년 전 0

기본적으로 각각의 대나무지역에서 상하좌우로 뻗어가며 BFS를 합니다.

하지만 그 지역이 이미 뻗어가려는 count보다 작으면 그 지역을 EnQueue하지 않는 방식으로 로직을 구성했습니다.

input data가 양의 정수라면 반례가 잘 생각나지 않습니다.

도와주세요 고수님들~!

#include <stdio.h>

typedef struct _node
{
	int x;
	int y;
}Node;

static long long Data[500][500] = {0, };
static int MaxCount[500][500] = {0, };
static Node Queue[250000] = {0, };
static int EnQueueIndex = -1;
static int DeQueueIndex = 0;
static int ItemCount = 0;
static int PX[4] = {-1, 1, 0, 0};
static int PY[4] = {0, 0, -1, 1};

void Init_Arrary(void);
void EnQueue(Node input);
Node DeQueue(void);
void DFS(int Count, int array_size);
void printf_array(int array_size);

int main(void)
{
	Init_Arrary();
	//freopen("input.txt", "r", stdin);
	//setbuf(stdout, NULL);
	int array_size, x, y, Maximum = 0;
	scanf("%lld", &array_size);
	
	for(x = 0; x < array_size; x++)
		for(y = 0; y < array_size; y++)
			scanf("%d ", &Data[x][y]);
	for(x = 0; x < array_size; x++)
		for(y = 0; y < array_size; y++)
		{
			int Count = 1;
			if(MaxCount[x][y] < Count)
			{
				Node temp;
				temp.x = x;
				temp.y = y;
				MaxCount[x][y] = Count++;
				EnQueue(temp);
				DFS(Count, array_size);
			}
			//printf_array(array_size);
			//printf("\n");
		}
	
		//printf_array(array_size);
	for(x = 0; x < array_size; x++)
		for(y = 0; y < array_size; y++)
			if(MaxCount[x][y] > Maximum)
				Maximum = MaxCount[x][y];

	printf("%d", Maximum);
}
void printf_array(int array_size)
{
	int x, y;
	for(x = 0; x < array_size; x++)
	{
		for(y = 0; y < array_size; y++)
			printf("%d ", MaxCount[x][y]);
		printf("\n");
	}
		
}
void DFS(int Count, int array_size)
{
	while(ItemCount)
	{
		int i;
		Node output = DeQueue();
		int nx = output.x;
		int ny = output.y;
		for(i = 0; i < 4; i++)
		{
			nx += PX[i];
			ny += PY[i];
			if(nx >= 0 && nx < array_size && ny >= 0 && ny < array_size)
			{
				if(Data[output.x][output.y] < Data[nx][ny])
				{
					if(MaxCount[nx][ny] <= MaxCount[output.x][output.y])
					{
						MaxCount[nx][ny] = MaxCount[output.x][output.y]+1;
						Node input;
						input.x = nx;
						input.y = ny;
						EnQueue(input);
					}
				}
			}
			nx = output.x;
			ny = output.y;
		}
	}
}
void EnQueue(Node input)
{
	if(EnQueueIndex == 250000)
		EnQueueIndex = 0;
	Queue[++EnQueueIndex] = input;
	ItemCount++;
}
Node DeQueue(void)
{
	if(DeQueueIndex == 250000)
		DeQueueIndex = 0;
	ItemCount--;
	return Queue[DeQueueIndex++];
}
void Init_Arrary(void)
{
	int i, j;

	for(i = 0; i < 500; i++)
		for(j = 0; j < 500; j++)
		{
			Data[i][j] = 0;
			MaxCount[i][j] = 0;
		}
}

phk707kr 7년 전 0

저도 같은 BFS로 풀려고 하고 있는데, 생각해보니 BFS는 사용하면 안되네요

왜냐하면 모든 지역을 다 탐색하니까요...

한방향을 선택했다면 팬더는 그 방향에서 최선의 길을 선택하고 아니면 죽어버려야 하니까 BFS는 좀 안맞는거 같아요,

죽어버린다는 뜻은, BFS를 더이상 실행하면 안되는거에요,

하지만 큐에 넣은 더 진행방향을 알아봐야하는 Node들이 있는 경우에는 팬더가 죽지않고, 다시 그 위치에서 탐색을 시작하겠죠...

맥시멈값도 자연스럽게 오를거고요 그래서 안되는거 같습니다.

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

문제

문제

출처

ICPC

무엇이 잘못되엇을까요?..... 잘 모르겠습니다.

ejgrt 7년 전 0

phk707kr 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말