글 읽기 - [c++] 시간초과!!ㅠ

kyungmin2579 6년 전 0

5000*5000 포문에서 시간이 많이걸리는걸까요??

어떻게 고쳐야할지 모르겠네요 ㅜㅜㅜ 조언해주세요

입력받은 위치에서 r번 1만큼 상,하,좌,우로 통신영역이 퍼지게 한 후

전체 arr에서 bfs로 덩어리를 세는 구조입니다

#include <iostream>
#include <queue>
using namespace std;

int arr[5000][5000];
int visit[5000][5000];
queue<pair<int,int> > q;

void set(int x, int y)
{
	int dx[4]={-1,1,0,0};
	int dy[4]={0,0,-1,1};

	for(int i=0; i<4; i++)
	{
		int a=x+dx[i];
		int b=y+dy[i];

		if(a>=0&&b>=0){
			if(a<5000&&b<5000)
			{
				arr[a][b]=1;
			}
		}
	}
}
void bfs()
{
	while(!q.empty())
	{
		int dx[4]={-1,1,0,0};
		int dy[4]={0,0,-1,1};

		int x = q.front().first;
		int y = q.front().second;

		for(int i=0; i<4; i++)
		{
			int a=x+dx[i];
			int b=y+dy[i];

			if(a>=0&&b>=0){
				if(a<5000&&b<5000)
				{
					if(arr[a][b]==1&&visit[a][b]==0)
					{
						visit[a][b]=1;
						q.push(make_pair(a,b));
					}
				}
			}
		}
		q.pop();
	}
}
int main()
{
	int t_case;
	cin>>t_case;

	for(int t=0; t<t_case; t++)
	{
		int n;
		cin>>n;
		int x, y, r;
		int count=0;

		for(int i=0; i<5000; i++)//초기화
		{
			for(int j=0; j<5000; j++){ 
				arr[i][j]=0;
				visit[i][j]=0;}
		}

		for(int i=0; i<n; i++)//입력받음
		{
			cin>>x>>y>>r;
			arr[x][y]=1;
			for(int j=0; j<r; j++)//통신영역 세팅 (탑으로부터 r번퍼짐)
			{
				set(x,y);
			}
		}
		for(int i=0; i<5000; i++)
		{
			for(int j=0; j<5000; j++)
			{
				if(arr[i][j]==1&&visit[i][j]==0)
				{
					visit[i][j]=1;
					q.push(make_pair(i,j));
					bfs();//덩어리세기
					count++;
				}
			}
		}
		cout<<count<<endl;
	}

	return 0;
}

최대 5000 인 y, x 를 담는 table 이 있고, r 을 이용해서 table 에서 어디랑 연결이 되는지 확인하기 위해서 table 을 모두 확인하는 것은 시간이 너무 걸리는 일이 될 것 같고.. (현재 코드에서 입력시에 최대 y, 최대 x 값을 기록해 두셨다가 for 으로 5000 까지 비교하지 마시고, 최대 y, 최대 x 값이랑 비교하도록 해보세요.. 아마 그래도 시간 초과 될 것 같네요..)

캠프 숫자가 3000 개니 3000 개에 대해서 전체 비교를 해서 (시간복잡도: N²) 관계 테이블을 만들고,

관계 테이블을 검색하는 방식입니다.

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

문제

문제

출처

ICPC

[c++] 시간초과!!ㅠ_ㅠ

kyungmin2579 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말