글 읽기 - 우선순위 큐 풀이법과 벡터를 이용한 풀이법의 시간 차이

ckeh0827 3년 전 0

아래는 시간초과가 나는 우선순위 큐로 풀이한 소스입니다.

비슷한 방식으로 벡터를 이용해서 탐색해가면서 sorting으로 나무에게 먹이를 주어도 시간초과가 나지 않는데 우선 순위
큐 방식은 시간 초과가 나는 이유가 궁금했습니다.

혹시 우선순위 큐에 데이터 삽입, 추출를 하는 경우 마다 내부에서 정렬이 수행돼서 더 시간이 오래걸린 건가요??

답변 부탁드립니다 :-)

#include <iostream>
#include <vector>
#include <queue>
#define MAX 11
using namespace std;

	//1. 봄 : 모든 나무는 자신의 나이만큼 양분을 먹고, 나이가 1증가
	//-> 각각의 나무는 1 * 1칸 안에 있는 양분만 먹을 수 있다.

	//   하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
	//   만약 먹을 양분이 없다면 즉사한다.

	//4. 여름 :  봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다
	//	나이를 2로 나눈 값이 양분으로 추가

	//5. 가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하고,
	//	인접한 칸 8개에 나이가 1인 나무가 생김

	//6. 겨울 : 로봇이 땅에 양분을 추가, 각 칸에 추가되는 양분은 A[r][c]로 입력으로 주어짐

	//출력 : K 년이 지난 후 살아있는 나무의 개수

int n, m, k;
int map[MAX][MAX];
int A[MAX][MAX];
int dx[] = { 1, -1, 0, 0, 1, -1,1 ,-1 };
int dy[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
// top에 가장 작은 수가 올라온다.
priority_queue<int, vector<int>, greater<int>> pq[MAX][MAX];
//class forest {
//public:
//	int x, y, age;
//	forest();
//	forest(int _x, int _y, int _age);
//	~forest() {}
//} typedef Tree;
//forest::forest() : x(0), y(0), age(0) {}
//forest::forest(int _x, int _y, int _age) : x(_x), y(_y), age(_age) {}

vector<pair<int, int>> v;
vector<pair<int, int>> born;
void Input()
{
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{

			scanf("%d", &A[i][j]);
			map[i][j] = 5;
		}
	}
	for (int i = 0; i < m; i++)
	{
		int x, y, age;
		scanf("%d %d %d", &x, &y, &age);
		pq[x][y].push(age);
	}

}

void SpringSummer()
{

	// 나무가 있는 곳들은 나이가 적은 나무부터 양분을 먹는다.
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (pq[i][j].empty()) continue;
			int x = i; int y = j;
			priority_queue<int, vector<int>, greater<int>> temp;
			int food = 0;

			// 있는 모든 나무가 양분을 먹으려고 시도
			while (!pq[x][y].empty())
			{
				// 양분을 먹을 수 있으면 
				if (map[x][y] - pq[x][y].top() >= 0)
				{
					// 먹는다
					map[x][y] -= pq[x][y].top();

					// 나무들이 번식할 위치
					if ((pq[x][y].top() + 1) % 5 == 0)
					{
						born.push_back(make_pair(x, y));
					}
					// 나이가 1 증가한상태로 다른 우선순위 큐에 저장
					temp.push(pq[x][y].top() + 1);
				}
				else {
					// 여름에 양분이 될 나무들
					food += (pq[x][y].top() / 2);
					// 먹을 수 없으면 전부 빼낸다.
				}
				pq[x][y].pop();
			}

			// pq[x][y]는 전부 비어진 상태, 살아있는 나무를 다시 넣는다.
			while (!temp.empty())
			{
				pq[x][y].push(temp.top());
				temp.pop();
			}
			// 여름
			map[x][y] += food;
		}
	}
}

void FallWinter()
{
	// 가을
	// 번식할 나무들
	for (auto tree : born)
	{
		int x = tree.first;
		int y = tree.second;

		for (int k = 0; k < 8; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			// 범위 벗어나면 out
			if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
			// 안벗어나면 나이 1짜리 나무 추가
			pq[nx][ny].push(1);
		}
	}

	// 겨울
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			// 양분 추가
			map[i][j] += A[i][j];
		}
	}
}

void Output()
{
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (!pq[i][j].empty())
			{
				ans += pq[i][j].size();
			}
		}
	}
	printf("%d", ans);
}
int main()
{
	Input();
	while (k--)
	{
		born.clear();
		SpringSummer();
		FallWinter();
	}
	Output();

	return 0;
}

caritas1996 3년 전 0

혹시 우선순위 큐에 데이터 삽입, 추출를 하는 경우 마다 내부에서 정렬이 수행돼서 더 시간이 오래걸린 건가요??

>> 넹

봄, 여름 처리 함수에서만 봐도 우선순위 큐 2개를 가지고 한쪽에 담고 다시 반대쪽으로 담은 연산을 하고 있으니

대충 2배정도 시간을 더 잡아먹겠네요.

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

문제

문제

출처

ICPC

우선순위 큐 풀이법과 벡터를 이용한 풀이법의 시간 차이

ckeh0827 3년 전 0

caritas1996 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말