글 읽기 - 시간초과가 납니다..

exceedlimit 4년 전 0

이보다 더 줄일 수 있는 방법이 생각이 안나는데.. 혹시 어느방향으로 수정하면 좋을 지 알려주실 수 있나요..?

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

//시간초과 미치겠네

int n,l,r;

int map[50][50];

int da[4] = { 0,1,0,-1 };
int db[4] = { 1,0,-1,0 };

struct Node {
	int a, b;
	Node(int _a, int _b) {
		a = _a; b = _b;
	}
};

Node temp = { 0,0 };

int check(vector<vector<int>> &visited) {
	//방문체크 안된곳이 있는지 확인
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == -1) {
				temp = { i,j };
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	cin >> n >> l >> r;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	int flag = 1;
	int ans = 0;

	while (flag) {
		flag = 0;
		vector<vector<int>> visited(n, vector<int>(n, -1));
		vector<vector<Node>> sector;//구역나눔
		vector<int> sum;
		int idx = 0;

		while (check(visited)) {
			//구역 나누어 주어야 하면
			queue<Node> q;
			q.push(temp);
			visited[temp.a][temp.b] = idx;
			sector.push_back(vector<Node>(0, { 0,0 }));
			sum.push_back(0);

			while (!q.empty()) {
				int a = q.front().a;
				int b = q.front().b;
				q.pop();
				sector[idx].push_back({ a,b });
				sum[idx] = sum[idx] + map[a][b];
				for (int i = 0; i < 4; i++) {
					int aa = a + da[i];
					int bb = b + db[i];

					if (aa < 0 || aa >= n || bb < 0 || bb >= n || visited[aa][bb] != -1) continue;
					//인구차가 범위 안이면
					if (abs(map[a][b] - map[aa][bb]) >= l && abs(map[a][b] - map[aa][bb]) <= r) {
						visited[aa][bb] = idx;
						q.push({ aa,bb });
						flag = 1;
					}
				}
			}
			idx++;
		}
		if (flag == 0) break;
		//구역별로 평균
		for (int i = 0; i < idx; i++) {
			int cnt = sector[i].size();//같은 구역갯수
			int average = sum[i] / cnt;
			//분배
			for (int j = 0; j < cnt; j++) {
				map[sector[i][j].a][sector[i][j].b] = average;
			}
		}
		ans++;
	}

	cout << ans;
}

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

문제

문제

출처

ICPC

시간초과가 납니다..

exceedlimit 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말