글 읽기 - 시간초과....

suniron94 6년 전 0

bfs로 푸는데 시간초과가 나는데 어찌해야하나요?

좀더 나은 방법이 어떤게 있을까요

#include <stdio.h>
int num, map[110][110],l, st=-1, ed=-1, chk[110][110], q[10100][2],temp,cnt, x, y, xz[4] = { 0, 0, 1, -1 }, yz[4] = { 1, -1, 0, 0 },min=9999,max=-1;
int chkarr(int x, int y)
{
	if (x >= num || x <0 || y>=num || y < 0)
		return -1;
	else return 1;
}
void clear()
{
	int i, j;
	for (i = 1; i <= num; i++)
		for (j = 1; j <= num; j++)
			chk[i][j] = 0;

	for (i = 0; i <= st; i++)
	{
		q[st][0] = 0; q[st][1] = 0;
	}
	st = 0, ed = 0; cnt = 0 , l=0;
	return;
}
int main()
{
	int i, j,k,size;
	scanf("%d", &num);
	size = num*num;
	for (i = 0; i < num; i++)
		for (j = 0; j < num; j++)
		{
			scanf("%d", &map[i][j]);
			if (min > map[i][j])
				min = map[i][j];
			if (max < map[i][j])
				max = map[i][j];
		}

	//x = 1; y = 1; q[++st][0] = 1; q[st][1] = 1;
	
	while (min<=max)
	{
		for (k = 0; k < num*num; i++)
		{
			x = k / num; y = k % num;
			if (chk[x][y] == 0 && map[x][y]!=-1) {
				q[++st][0] = k / num; q[st][1] = k % num;
				chk[k / num][k % num]++;
			}
			else
				continue;
			while (st != ed)
			{
				x = q[++ed][0];  y = q[ed][1];

				if (l == 0){
					for (i = 0; i < num; i++)
					{
						for (j = 0; j < num; j++)
						{
							if (map[i][j] <= min)
								map[i][j] = -1;
						}
					}
				}  l++;
				for (i = 0; i < 4; i++)
				{
					if (chkarr(x + xz[i], y + yz[i])==1 && chk[x + xz[i]][y + yz[i]] == 0 && map[x + xz[i]][y + yz[i]] != -1)
					{
						q[++st][0] = x + xz[i]; q[st][1] = y + yz[i];
						chk[x + xz[i]][y + yz[i]]++;
					}
				}
			}
			cnt++;
		}
		if (temp < cnt)
			temp = cnt;
		clear();
		min++;
	}

	printf("%d", temp);

	return 0;
}

fresmic 6년 전 0

저도 BFS로 풀었는데, 시간 안에 통과했습니다!

Queue를 항상 0으로 초기화 해야할 필요가 있을까요~?

Queue를 초기화 하면서 O(10100) * 100 이 소요될거 같네요..

또, BFS 시작 전 map[i][j] = -1 로 두는 작업도 O(n^2)이라, 해당 부분도 잘 생각해보시면 통과할 수 있을거 같아요! :D

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

문제

문제

출처

ICPC

시간초과....

suniron94 6년 전 0

fresmic 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말