글 읽기 - 2842번 지적 좀 해주세요..

wnsduds1 2년 전 0

죄송합니다..제가 저는 도저히 제코드의 잘못된 부분을 못찾겠습니다..

간곡히 도움을 요청합니다..ㅠㅠㅠ

map 배열 -> 우체국과 목초지 배달지점의 정보를 담는 char배열

x배열->map의 피로도를 가지고 있는 배열

arr배열-> x배열을 펼치고 오름차순 정렬한 배열

index배열 -> x배열 중복제거할려고 만든 배열

bfs돌려서 모든 집에배달이 가능하면 left++

모든집에 배달이 불가능하면 right++을 수행하여 답을 구했습니다.

대회 tc를 받아서 정말 전부 돌려보았는데 정말 다 맞았습니다.

sort부분은 문제가 없는 것으로 확인됬습니다. 퀵소트 버블소트 모두 사용해보았는데 55퍼에세 계속 틀려서..

53~71줄에서 문제가 있거나

bfs함수에 문제가 있는 것 같습니다.

bfs내 함수에서도 큐의 사이즈를 2501로도 해보았고 25001로도 해보았습니다. 사이즈 문제는 아닌 것 같습니다.

따끔한 지적 부탁드리겠습니다!

c11입니다!

typedef struct list {
	int id, kd;
}list;
int x[51][51];
void q_sort(int arr[], int index_s, int index_e);
int BFS(char map[][51],list start, int left,int right,int k,int n);
int fix_left, fix_right;
int index[1000001] = { 0, };
int main()
{
	list start;
	char map[51][51];
	int arr[2501];
	int n, i, j, k, pre,size;
	int tmp;
	int min=987654321;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%s", map[i]);
	j = 0;
	for (i = 0; i < n; i++)
	{
		for (k = 0; k < n; k++)
		{
			scanf("%d", &x[i][k]);
			if (index[x[i][k]] == 0)
			{
				index[x[i][k]] = 1;
				arr[j++] = x[i][k];
			}
		}
	}
	size = 0;
	
	for (i = 0; i < n; i++)
	{
		for (k = 0; k < n; k++)
		{
			if (map[i][k] == 'P')
			{
				start.id = i;
				start.kd = k;
			}
			else if (map[i][k] == 'K')
			{
				size += 1;
			}
		}
	}
	q_sort(arr, 0, j - 1);
	fix_left = 0;
	fix_right = 0;
	while (fix_right<j&&fix_left<=fix_right)
	{
		while (1)
		{
			tmp = BFS(map, start, arr[fix_left], arr[fix_right], size, n);
			if (tmp == 1)
			{
				pre = arr[fix_right] - arr[fix_left];
				min = min > pre ? pre : min;
				fix_left += 1;
			}
			else {
				break;
			}
		}
		fix_right += 1;
		
	}
	printf("%d",min);

	return 0;
}

int BFS(char map[][51], list start, int left, int right, int k1, int n)
{
	list que[25001];
	int visit[51][51] = { 0, };
	int i, k;
	int front = -1, back = 0;
	int index_i, index_k, cnt = 0;
	que[back] = start;
	visit[que[back].id][que[back].kd] = 1;
	while (front < back)
	{
		front += 1; 
		
		for (i = -1; i <= 1; i++)
		{
			for (k = -1; k <= 1; k++)
			{
				if (!(i == 0 && k == 0))
				{
					index_i = que[front].id + i;
					index_k = que[front].kd + k;
					if (index_i >= 0 && index_i < n&&index_k >= 0 && index_k < n)
					{
						if (visit[index_i][index_k] == 0)
						{
							visit[index_i][index_k] = 1;
							if (left <= x[index_i][index_k] && x[index_i][index_k] <= right)
							{
								back += 1;
								que[back].id = index_i;
								que[back].kd = index_k;
								if (map[index_i][index_k] == 'K')
								{
									cnt += 1;
								}

							}
						}
						
					}

				}
			}
		}
	}
	if (cnt == k1)
	{
		return 1;
	}
	else {
		return -1;
	}
}
void q_sort(int arr[], int index_s, int index_e)
{
	int L = index_s, R = index_e;
	int pit = (L + R) / 2;
	int tmp;
	if (index_s >= index_e)
		return;
	while (L < R)
	{
		while (L < R&&arr[L] < arr[pit])
			L++;
		while (L < R&&arr[R] >= arr[pit])
			R--;
		if (L == pit)
			pit = R;

		tmp = arr[R];
		arr[R] = arr[L];
		arr[L] = tmp;
	}
	tmp = arr[R];
	arr[R] = arr[pit];
	arr[pit] = tmp;
	pit = R;
	q_sort(arr, index_s, pit - 1);
	q_sort(arr, pit + 1, index_e);
}

wnsduds1 2년 전 2

우체국이 left ,right범위내에 없었을 때도 출발 한 것이 문제였습니다..

ophelia172 1년 전 0

와 정말 감사합니다..... 덕분에 겨우 해결했습니다

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