글 읽기 - 시간을 줄일 수 있는 방법이 있을까요??

iklj123 4년 전 0

음 75%대에서 시간이 계속 초과 뜨는데 혹시 시간을 줄일 수 있는 효과적인 방법이 있을 까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>

using namespace std;

int N, L, R;
vector<vector<int>>map;
vector <vector<bool>> visited;
vector<vector<int>>adj;
vector<pair<int, int>> ind;
int c = 0;
typedef struct {
	int y, x;
}Dir;

Dir moveDir[4] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
Dir confirmDir[2] = { { 0,1 },{ 1,0 } };

void bfs(int y, int x)
{
	queue<pair<int, int>> q;
	ind.clear();
	int sum = 0;
	int cnt = 1;
	visited[y][x] = true;

	q.push(make_pair(y, x));
	ind.push_back(make_pair(y, x));  //우선 지금 연합에 포함되는 나라들 추가( 후에 이 나라들에 계산된 값 다 넣어줄거임)

	while (!q.empty())
	{
		int yy = q.front().first;
		int xx = q.front().second;
		sum += map[yy][xx];
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int yyy = yy + moveDir[i].y;
			int xxx = xx + moveDir[i].x;

			if (yyy >= 0 && yyy < N&& xxx >= 0 && xxx < N && !visited[yyy][xxx] && adj[(yy*N) + xx][(yyy*N) + xxx] == 1)
			{
				q.push(make_pair(yyy, xxx));
				ind.push_back(make_pair(yyy, xxx));
				visited[yyy][xxx] = true;
				cnt++;
			}
		}
	}

	int res = sum / cnt;

	for (int i = 0; i < (int)ind.size(); i++)
	{

		map[ind[i].first][ind[i].second] = res;

	}

}

int main()
{
	int a = 0;
	cin >> N >> L >> R;
	map = vector<vector<int>>(N, vector<int>(N, 0));
	for (int i = 0; i<N; i++)
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
		}
	int howmany = 0;
	while (1) {
		visited = vector<vector<bool>>(N, vector<bool>(N, false));
		adj = vector<vector<int>>(N*N, vector<int>(N*N, 0));
		howmany = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				for (int k = 0; k < 2; k++)
				{
					int yy = i + confirmDir[k].y;
					int xx = j + confirmDir[k].x;
					if (yy >= 0 && yy < N && xx >= 0 && xx < N&& abs(map[yy][xx] - map[i][j]) >= L && abs(map[yy][xx] - map[i][j]) <= R)
					{
						adj[(i*N) + j][(yy*N) + xx] = 1;
						adj[(yy*N) + xx][(i*N) + j] = 1;

						howmany++;

					}
				}
			}
		}
		c++;
		if (howmany == 0)
		{
			c--;
			break;
		}
		for (int s = 0; s < N; s++)
		{
			for (int t = 0; t < N; t++)
			{
				if (!visited[s][t]) {

					bfs(s, t);

				}
			}
		}

		visited.clear();
		adj.clear();
	}

	cout << c << endl;




	return 0;
}

qahira 4년 전 1

adj를 매번 초기화하고 하기위해 새로 할당받아 쓰시는데, clear()하고 쓰는건 어떨까요? 굳이 새로 생성하실 필요는 없어보입니다.

굳이 벡터일 이유도없어보이고요.

adj배열을 N이 최대일떄를 가정하고 만들고선

int adj[N ][N]; 으로 선언하고

bfs하기전에 초기화를 memset(adj, 0. sizeof(int)*N*N)같은 식으로 써도 괜찮을것 같아요

댓글 쓰기

iklj123 4년 전 0

조언 감사합니다!

qahira 4년 전 0

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

문제

문제

출처

ICPC

시간을 줄일 수 있는 방법이 있을까요??

iklj123 4년 전 0

qahira 4년 전 1

iklj123 4년 전 0

qahira 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말