191015 백준 알고리즘 문제풀기

|

[16235] 나무 재테크

  • 난이도: 상
    • 문제 이해 30분, 구현하는데 40분, 디버깅 1시간정도 걸렸다.
    • 결국 시간 복잡도때문에 틀렸다.
    • 아무래도 우선순위 큐를 사용하다보니 늦어졌고, 게다가 이중 for문으로 하나하나 좌표단위로 접근하다보니 틀린듯 하다.
    • 모든 문제는 풀기에 앞서 정확하게 조건을 이해하고, 정리하고, 직접 어떻게 되는지 손으로 풀어보고 이해한다음에 풀기 시작하면 못 풀 문제는 없을것이라 생각한다..
    • 하지만 맞게 풀었다고 무조건 맞는것도 아닌듯하다 ㅠㅠ
      • 시간복잡도..
    • 만약 시험에 나왔으면 시간복잡도때문에 틀렸다.
  • 문제
    • https://www.acmicpc.net/problem/16235
    • 정사각형 맵의 크기 N, 나무의 개수 M, 햇수 K가 순서대로 입력됨
    • 다음으로, 각 맵에 매 해 겨울 줄 비료상태가 입력됨
    • 마지막으로 M개의 나무 좌표와 나무 나이가 입력 됨
    • 조건
      • 한 칸에는 여러개의 나무가 존재 할 수 있다.
        • 이게 핵심 조건
      • 가장 처음 땅에 있는 양분은 모두 5다.
      • 봄에는
        • 자신 나이만큼 나무가 양분을 먹고 나이가 1 증가한다.
        • 자신이 존재하는 칸의 양분만 섭취 가능하다.
        • 한 칸에 여러 나무가 존재시, 나이 어린 나무부터 양분을 섭취한다.
        • 만약 땅에 양분이 부족해 나이만큼 양분을 먹지 못하면 즉시 사망한다.
      • 여름에는
        • 봄에 죽은 나무가 양분이 된다.
        • 양분이 되는 죽은 나무는 나이를 2로 나눈 값이 해당 칸의 양분으로 더해진다.(소숫점 버림)
      • 가을에는
        • 나무가 번식한다.
        • 나이가 5의 배수일 때만 번식한다.
        • 땅 범위를 벗어나는 번식은 하지 않는다.
        • 인접한 8개 칸에 나이 1인 나무가 새로 생성된다.
      • 겨울에는
        • 땅에 로봇이 양분을 추가한다.
        • 추가되는 양분은 위에서 비료상태로 입력된다.
  • 풀이
    • 우선순위 큐 이용
      • 우선순위 큐는 큐에 새로 입력되는 데이터가 어떠한 정렬 순서에 따라 정렬되어 자기 자리를 찾아간다.
      • C++ STL에서는 <queue>에서 제공된다.
        • priority_queue<data_type, container<data_type>, order<data_type>> pq_name
          • ex. priority_queue<int, vector<int>, greater<int>> pq
          • greater 규칙을 따르면 가장 작은 값이 pq.top()에 존재한다.
          • 반대로 less 규칙을 따르면 가장 큰 값이 pq.top()에 존재한다.
    • 우선순위 큐를 2차원 배열 형태로 이용한다면 시간초과로 문제가 틀린다.
      • 아래 코드는 틀린 문제 풀이 코드(정답은 맞지만 시간조건을 초과함)
      • 다양한 방법으로 for문을 최소화해봤지만 소용없다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int biryo[11][11];
int dead[11][11];
int curmap[11][11];

int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };

priority_queue<int, vector<int>, greater<int>> c_tree[11][11]; // 작은게 맨 위로
priority_queue<int, vector<int>, greater<int>> n_tree[11][11];

void init_curmap(int N)
{
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			curmap[j][i] = 5;
		}
	}
}

int main()
{
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	
	//비료맵 저장
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &biryo[i][j]);
		}
	}

	//나무 저장
	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		c_tree[y][x].push(z);
	} // c_tree에는 해당 좌표에 나무 크기가 순서대로 저장됨


	int year = K;
	// 맵 초기화
	init_curmap(N);

	while (year--)
	{//년수동안
		//봄
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (c_tree[j][i].size() != 0)
				{// 현재 위치 나무가 존재한다면
					while (!c_tree[j][i].empty())
					{//현재 위치 나무들동안 나이가 어린 나무부터
						int cur_size = c_tree[j][i].top();
						c_tree[j][i].pop(); // 현재 나무를 뽑아서
						if (curmap[j][i] >= cur_size)
						{//만약 해당 위치 양분이 현재 나이보다 많다면
							curmap[j][i] -= cur_size; // 양분 먹고
							n_tree[j][i].push(cur_size + 1); // 나이 1 증가해서 다음 맵에저장
							continue;
						}
						else
						{//해당 위치 양분이 나이보다 부족하다면
							dead[j][i] += int(cur_size / 2); // 죽은 나무가 되어 반 크기의 양분이 됨
						}
					}
				}

				//여름, 겨울 비료주기
				curmap[j][i] += dead[j][i];
				curmap[j][i] += biryo[j][i];
				dead[j][i] = 0; // dead 초기화

			}
		}
		////여름, 겨울(비료 주기)
		//for (int j = 1; j <= N; j++)
		//{
		//	for (int i = 1; i <= N; i++)
		//	{
		//		//죽은 나무는 양분이 된다.
		//		curmap[j][i] += dead[j][i];
		//		curmap[j][i] += biryo[j][i];
		//		dead[j][i] = 0; // dead 초기화
		//	}
		//}
		//가을 (나무 번식)
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (n_tree[j][i].size() != 0)
				{// 만약 현재위치 나무가 존재한다면
					while (!n_tree[j][i].empty())
					{// 현재위치 나무들동안
						int cur_size = n_tree[j][i].top(); // 현재 나무 크기 저장
						n_tree[j][i].pop(); // 현재 나무 뽑고
						if (cur_size % 5 == 0)
						{//만약 현재 나무가 번식조건이라면(5의 배수)
							for (int k = 0; k < 8; k++)
							{
								int nx = i + dx[k]; // 다음위치 찾고
								int ny = j + dy[k];
								if (nx < 1 || N < nx||ny < 1 || N < ny) continue; // 범위 안이라면
								c_tree[ny][nx].push(1); // 현재 맵의 다음 위치에 번식
							}
							c_tree[j][i].push(cur_size); // 현재 맵에 현재 나무 옮겨심기
						}
						else
						{//만약 나무가 번식조건이 아니라면
							c_tree[j][i].push(cur_size); // 다음 맵에 나무를 옮겨심는다
						}
					}
				}
			}
		}
		//겨울 비료주기는 여름에
	}

	// 나무 개수 세기
	int cnt = 0;
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			if (c_tree[j][i].size() != 0)
			{//나무 있으면
				while (!c_tree[j][i].empty())
				{//나무들을
					c_tree[j][i].pop();//뽑고
					cnt++; //센다.
				}
			}
		}
	}

	printf("%d\n", cnt);
	//std::system("pause");
	return 0;
}
  • 이 문제를 덱을 이용해서 풀면 다음과 같다
    • 덱을 이용하면 시간초과 문제를 해결 할 수 있고(sorting 없으니까) 문제를 통과할 수 있다.
    • 문제에서 입력으로 주어지는 나무의 위치는 모두 서로 다름 조건을 잘 고민해보면 덱으로 풀 수 있는 문제라는 힌트를 얻을 수 있었다.
      • 문제를 꼼꼼히 읽는게 최고의 방법인듯 하다.
    • 덱은 앞에서 자료를 넣고 빼고, 뒤에서 넣고 빼고 할 수 있다.
    • 위 코드에서 우선순위 큐를 덱으로만 바꾸고 중간에 코드 살짝만 바꾸면 된다.
      • 어떠한 좌표에서 나무 나이가 작은 값이 맨 오른쪽으로, 큰 값이 맨 왼쪽으로 가야한다.
      • 덱에서 새로 생성되는 나무들은 무조근 크기가 작으니까 push_back으로 넣으면 된다.
      • 2 개의 덱을 번갈아가며 사용하기 때문에, 새로 생성되는 나무는 무조건 오른쪽(back)에서 넣고, 기존 나무는 왼쪽(front)에서 넣으면 순서는 항상 바뀔 수 없다.
        • pop은 무조건 back에서만, push는 새 나무는 back, 큰 나무는 front에서 push!
        • 이 순서만 지키면 무조건 순서는 정렬되어있게 된다.
    • 자세한건 밑에 코드 참조
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>

using namespace std;

int biryo[11][11];
int dead[11][11];
int curmap[11][11];

int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };

deque<int> c_tree[11][11];
deque<int> n_tree[11][11];

int main()
{
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);

	//비료맵 저장
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &biryo[i][j]);
			curmap[j][i] = 5; // 처음 비료 초기화
		}
	}

	//나무 저장
	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		c_tree[y][x].push_front(z); // 일단은 그냥 순서 상관없이 집어넣는다. 어차피 입력되는 나무의 위치는 모두 다르니까.
	} // c_tree에는 해당 좌표에 나무 크기가 저장

	int year = K;

	while (year--)
	{//년수동안
	 //봄
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (c_tree[j][i].size() != 0)
				{// 현재 위치 나무가 존재한다면
					while (!c_tree[j][i].empty())
					{//현재 위치 나무들동안
						int cur_size = c_tree[j][i].back(); // 뒤쪽에서 어린 나무부터 뽑아낸다.
						c_tree[j][i].pop_back();
						if (curmap[j][i] >= cur_size)
						{//만약 해당 위치 양분이 현재 나이보다 많다면
							curmap[j][i] -= cur_size; // 양분 먹고
							n_tree[j][i].push_front(cur_size + 1); // 나이 1 증가해서 다음 맵에 앞으로 집어넣는다.
							continue;
						}
						else
						{//해당 위치 양분이 나이보다 부족하다면
							dead[j][i] += int(cur_size / 2); // 죽은 나무가 되어 반 크기의 양분이 됨
						}
					}
				}

				//여름, 겨울 비료주기
				curmap[j][i] += dead[j][i];
				curmap[j][i] += biryo[j][i];
				dead[j][i] = 0; // dead 초기화

			}
		}
		
		//가을 (나무 번식)
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= N; i++)
			{
				if (n_tree[j][i].size() != 0)
				{// 만약 현재위치 나무가 존재한다면
					while (!n_tree[j][i].empty())
					{// 현재위치 나무들동안
						int cur_size = n_tree[j][i].back(); // 가장 작은 나무부터
						n_tree[j][i].pop_back(); // 현재 나무 뽑고
						if (cur_size % 5 == 0)
						{//만약 현재 나무가 번식조건이라면(5의 배수)
							for (int k = 0; k < 8; k++)
							{
								int nx = i + dx[k]; // 다음위치 찾고
								int ny = j + dy[k];
								if (nx < 1 || N < nx || ny < 1 || N < ny) continue; // 범위 안이라면
								c_tree[ny][nx].push_back(1); // 현재 맵의 다음 위치에 번식
							}// 나무 번식은 무조건 제일 작은 나무 크기이므로 덱의 뒤에서 집어넣는다.
							c_tree[j][i].push_front(cur_size); // 현재 맵에 현재 나무 옮겨심기
						}// 현재 나무는 무조건 큰 나무일 것이므로 덱 앞에 집어넣는다.
						else
						{//만약 나무가 번식조건이 아니라면
							c_tree[j][i].push_front(cur_size); // 그냥 다음 맵에 나무를 옮겨심는다(앞으로 넣어야 함)
						}
					}
				}
			}
		}
		//겨울 비료주기는 여름에 완료
	}

	// 나무 개수 세기
	int cnt = 0;
	for (int j = 1; j <= N; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			cnt += c_tree[j][i].size(); // 해당 위치 사이즈가 곧 나무 갯수이므로
		}
	}

	printf("%d\n", cnt);

	//std::system("pause");
	return 0;
}
  • 쉬운줄 알고 덤벼보면 문제는 꼭 항상 어렵다.