3-C 실행 시간 질문드립니다.

작성한 질문수 25

0

안녕하세요 Grid님ㅎㅎ

해당 코드에 주석을 달아봤는데요. 참고부탁드립니다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

const int dys[4] = { -1, 1, 0, 0 };
const int dxs[4] = { 0, 0, -1, 1 };

void update(int i, int j, int N, int L, int R, bool& flag, bool visited[][51], int MAP[][51])
{
	vector<pair<int, int>> union_group;
	queue<pair<int, int>> q;
	int populations = MAP[i][j];
	int cnt = 1;
	union_group.push_back({ i, j });
	q.push({ i, j });
	visited[i][j] = true;
	while (q.empty() == false)
	{
		pair<int, int> curr = q.front();
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int ny = curr.first + dys[k];
			int nx = curr.second + dxs[k];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N || abs(MAP[ny][nx] - MAP[curr.first][curr.second]) < L || abs(MAP[ny][nx] - MAP[curr.first][curr.second]) > R)
				continue;
			if (visited[ny][nx])
				continue;
			if (flag == false)
				flag = true;
			populations += MAP[ny][nx];
			cnt += 1;
			union_group.push_back({ ny, nx });
			q.push({ ny, nx });
			visited[ny][nx] = true;
		}
	}
	for (int i = 0; i < union_group.size(); i++)
	{
		MAP[union_group[i].first][union_group[i].second] = populations / cnt;
	}
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// 전역변수를 사용해주세요. : 교안 참고
   int answer = 0;
	int N, L, R;
	cin >> N >> L >> R;
	int MAP[51][51];
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> MAP[i][j];
		}
	}
	while (true)
	{
		bool flag = false;
		bool visited[51][51];
      // 한번에 초기화 가능합니다. for문 쓰지 않아도.
		for (int i = 0; i < N; i++)
			memset(visited[i], false, sizeof(bool) * N);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (visited[i][j] == false)
				{
					update(i, j, N, L, R, flag, visited, MAP);
				}
			}
		}
		if (flag == false)
			break;
		answer += 1;
	}
   //endl을 쓰지 말아야 합니다. : 교안참고
	cout << answer << endl;
}