글 읽기 - 다른 코드와 뭔 차이 때문에 시간이 오래 걸리는지 모르겠습니다

ajh1973456 2년 전 0

문제를 맞추긴 했는데, 밑의 코드로 440ms가 나와서 시간이 오래 걸린다고 생각하여 다른 분들의 c++ 코드를 봤습니다.

큐를 안 쓰신 것 빼곤 저와 별다른 차이점이 없어보였는데, 그 코드는 80ms였습니다.

제 코드에서 어떤 점 때문에 시간이 오래 걸리는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
};

int n, l, r, map[51][51];
bool visited[51][51];
pos dir[4] = { {-1,0}, {0,-1}, {1,0}, {0,1} };
vector<pos> group;

bool movable(pos& next) {
	return { next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= n
	&& !visited[next.x][next.y] };
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> l >> r;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}

	int ans = 0;
	while (1) {
		memset(visited, 0, sizeof(visited));

		bool escape = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (!visited[i][j]) {
					queue<pos> bfs;
					group.clear();
					bfs.push({ i,j });
					visited[i][j] = 1;
					group.push_back({ i,j });
					int total = map[i][j];
					
					while (!bfs.empty()) {
						pos now = bfs.front();
						int people = map[now.x][now.y];
						bfs.pop();
						
						for (int k = 0; k < 4; k++) {
							pos next = { now.x + dir[k].x, now.y + dir[k].y };
							if (movable(next)) {
								if (abs(map[next.x][next.y] - people) >= l
									&& abs(map[next.x][next.y] - people) <= r) {
									visited[next.x][next.y] = 1;
									group.push_back(next);
									bfs.push(next);
									total += map[next.x][next.y];
								}
							}
						}
					}

					if (group.size() > 1) {
						escape = 0;
						int dvd = total / group.size();
						for (auto& k : group) {
							map[k.x][k.y] = dvd;
						}
					}
				}
			}
		}

		if (escape) {
			cout << ans;
			exit(0);
		}
		else ans++;
	}
}

luitz79 8달 전 0

queue를 썼기 때문에 느린겁니다.

queue는 list입니다.

list의 장점은 앞부분에서의 삽입/삭제가 용이한 점이 있지만

끝부분에서만 삽입/삭제가 일어날 경우 array가 속도가 훨씬 빠릅니다.

vector도 어떻게 쓰느냐에 따라 속도의 격차가 커질 수 있습니다.

지금 코드에서는 queue를 쓰지 않아도 됩니다.

이렇게 고쳐놓고 보니 group과 bfs가 중복이군요.

지금 아래 코드가 96ms고 중복 제거하면 88ms 나옵니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
	pos(int x, int y) : x(x), y(y) {}
};

int n, l, r, map[51][51];
bool visited[51][51];
pos dir[4] = { {-1,0}, {0,-1}, {1,0}, {0,1} };
vector<pos> group;

bool movable(pos& next) {
	return { next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= n
	&& !visited[next.x][next.y] };
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	vector<pos> bfs;
	bfs.reserve(2501);
    group.reserve(2501);

	cin >> n >> l >> r;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}

	int ans = 0;
	while (1) {
		memset(visited, 0, sizeof(visited));

		bool escape = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (!visited[i][j]) {
					bfs.clear();
					group.clear();
					bfs.emplace_back(i, j);
					visited[i][j] = 1;
					group.emplace_back(i, j);
					int total = map[i][j];

					for (int aa = 0; aa < bfs.size(); aa++)
					{
						pos now = bfs[aa];
						int people = map[now.x][now.y];

						for (int k = 0; k < 4; k++) {
							pos next = { now.x + dir[k].x, now.y + dir[k].y };
							if (movable(next)) {
								if (abs(map[next.x][next.y] - people) >= l
									&& abs(map[next.x][next.y] - people) <= r) {
									visited[next.x][next.y] = 1;
									group.emplace_back(next);
									bfs.emplace_back(next);
									total += map[next.x][next.y];
								}
							}
						}
					}

					if (group.size() > 1) {
						escape = 0;
						int dvd = total / group.size();
						for (auto& k : group) {
							map[k.x][k.y] = dvd;
						}
					}
				}
			}
		}

		if (escape) {
			cout << ans;
			exit(0);
		}
		else ans++;
	}
}

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

문제

문제

출처

ICPC

다른 코드와 뭔 차이 때문에 시간이 오래 걸리는지 모르겠습니다

ajh1973456 2년 전 0

luitz79 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말