글 읽기 - 시간초과) 어딜고쳐야하는지 조언부탁드립니다

rbbinit 5년 전 0

백준에서 돌려보면

78%에서 시간초과가 뜨는데

제가 시간초과가 자주일어나는편이긴 한데..

그럴때마다 어떻게바꿔야 할지 감이안오는데

혹시 시간복잡도 계산법을 익히고와야 할까요?

조언 해주시면 감사하겠습니다

#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <functional>
#include <queue>
#include <stack>
#include <set>
using namespace std;

int N, L, R; //N 1~50, L,R 1~100
int a[51][51]; //인구수
			   //인구차가 L명이상, R명이하 ->국경선열림
const int dr[4] = { 1,0,-1,0 };
const int dc[4] = { 0,-1,0,1 };
int vis[51][51];
int vis2[51][51];
queue<pair<int, int>>q;
int sum, k;
int ans;
int result;

void adds()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (vis2[i][j])
			{
				a[i][j] = sum / k;
			}
		}
	}
	//cout << "sum" << sum << " " << k << "\n";
	sum = 0; k = 0;
	memset(vis2, 0, sizeof(vis2));
}

void bfs(int x, int y)
{
	
	q.push({ x, y });
	vis[x][y] = 1;
	sum += a[x][y];
	++k;

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;
		q.pop();
		vis[xx][yy] = 1;
		vis2[xx][yy] = 1;
		for (int i = 0; i < 4; i++)
		{
			int xxx = xx + dr[i];
			int yyy = yy + dc[i];
			if (xxx < 0 || yyy < 0 || xxx >= N || yyy >= N) continue;
			if (vis[xxx][yyy]) continue;

			if (abs(a[xx][yy] - a[xxx][yyy]) >= L && abs(a[xx][yy] - a[xxx][yyy]) <= R)
			{
				++ans;
				q.push({ xxx, yyy });
				vis[xxx][yyy] = 1;
				vis2[xxx][yyy] = 1;
				sum += a[xxx][yyy];
				++k;
			}
		}
	}
	adds();
	//vis, sum, k초기화 추가
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> a[i][j];
		}
	}

		
	while (1)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (!vis[i][j])
				{
					bfs(i, j); //1번돌고 모든값을 평균으로
				}
			}
		}		
		memset(vis, 0, sizeof(vis));
		if (ans == 0)
		{
			cout <<  result;
			return 0;
		}
		++result;
		ans = 0;
		
	}
	
}

jsjsjs0775 5년 전 2

지금 bfs 구조가

for(for(bfs)) 이거 라면, bfs 끝난 후 해당 결과에 대해 바로 인구값을 바꾸지마시고

for(for(bfs))를 모두 돌고나서 한 번에 인구값을 바꾸도록 짜면 시간초과가 안날거에요

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

문제

문제

출처

ICPC

시간초과) 어딜고쳐야하는지 조언부탁드립니다

rbbinit 5년 전 0

jsjsjs0775 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말