[BOJ/백준 16235/C++] 나무 재테크
https://www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
[문제 요약]
- 상도는 최근 N×N 크기의 땅을 구매했다.
- 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다.
- 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
- 상도는 나무 재테크로 더 큰 돈을 벌기 위해 M개의 나무를 구매해 땅에 심었다. 같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.
- 이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다.
(봄)
- 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
(여름)
- 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
(가을)
- 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
(겨울)
- 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하여라.
[문제 조건]
- 첫째 줄에 N, M, K가 주어진다.
- 1 ≤ N ≤ 10
- 1 ≤ M ≤ N2
- 1 ≤ K ≤ 1,000
- 둘째 줄부터 N개의 줄에 A배열의 값이 주어진다. r번째 줄의 c번째 값은 A[r][c]이다.
- 다음 M개의 줄에는 상도가 심은 나무의 정보를 나타내는 세 정수 x, y, z가 주어진다. 처음 두 개의 정수는 나무의 위치 (x, y)를 의미하고, 마지막 정수는 그 나무의 나이를 의미한다.
- 1 ≤ A[r][c] ≤ 100
- 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
- 입력으로 주어지는 나무의 위치는 모두 서로 다름
- 시간 제한 : 0.3초
- 메모리 제한 : 512MB
[문제 풀이]
시간제한이 무려 0.3초다. 가능한 최대로 시간을 줄여야 한다는 것이다.
문제를 읽어보고 어떤 순서로 만들어야 될지 생각해보자.
먼저 봄에는 나무들이 양분을 나이만큼 흡수한 뒤 나이를 한살 먹는다. 하지만 남은 양분이 나이 보다 적을 경우 양분을 흡수하지 못하고 죽은나무가 된다.
이때 죽은나무들은 여름에 그 자리에 양분으로 변한다.
여기까지 먼저 봤을때 죽은 나무들이 판단되는 때는 봄에 판단이 된다. 따라서 봄에 살 수 있는 나무와 죽을 나무를 서로 나누는 작업이 필요하고, 여름에 죽은나무들의 정보를 일괄로 처리해주면 되는 것이다.
다음으로 가을에는 나이가 5의배수인 나무들이 나무의 위치를 기준으로 8방향에 나이가 1인 나무가 새로 생긴다.
가을에 번식할 나무도 봄에 결정을 할 수 있다. 양분을 흡수하여 나이가+1될때 5의배수가 되면 따로 번식할 나무들의 정보를 저장해놓은 뒤 가을에 번식을 진행해주면된다.
겨울에는 시뮬레이션이 돌아가는 맵에다가 입력으로 주어진 2차원배열을 추가로 더해주면된다.
이렇게 정리할 수 있다.
각 계절에 어떤 작업을 할지 정리가 되었다. 하지만 가장 중요한 시뮬레이션을 돌릴 맵을 어떤식으로 나타낼 것인가.
먼저 처음에 땅을 2차원배열로 나타내고 나무들을 우선순위 큐에 나이가 작은 순서대로 저장하는 방식을 사용했고, 여름에 죽을 나무들은 순서에 상관이 없으니 Vector를 이용해서 죽은나무들을 처리했고, 가을에는 우선순위 큐에 들어있는 나무들을 하나씩 확인해서 나이가 5의 배수면 번식을 하는 방식을 이용했었다.
하지만 시간초과가 났다. 아마도 이유는 우선순위 큐에 나무를 집어넣거나 빼는 연산을 할때 내부적으로 계속정렬을 진행하다보니 시간초과가 걸린 것 같다.
다음에 사용했던 자료구조는 list를 사용했는데, 처음에 나무들을 입력할때 한번만 정렬해주고, 봄에 죽을나무들은 list에서 제거시키고, 살아남을 나무들은 다 같이 나이가 1씩 증가되니 자동으로정렬이 되어있을 것이다. 가을에는 어차피 나이가1인 나무들만 추가됨으로 맨 앞에 추가하는 방식을 사용했는데 이 방법 역시 시간초과가 걸렸다.
list를 쓰는 방법은 필자가 아직 숙달되지 않아서 시간초과가 난 것 같아서 이 방법은 나중에 다시 시도해보도록 하자.
마지막으로 썻던 방법은 2차원 배열 각 원소가 Vector 컨테이너를 갖고 있고, 이 Vector에는 나무들의 나이가 들어가 있다.
따라서 봄에 2차원배열을 하나하나씩 확인하면서 나무 나무들을 오름차순으로 정렬하고, 살아남을나무와 죽을나무를 구분 짓고 여름과 가을에는 일반 큐를 사용하여 제거와 번식을 진행시켰다. 그랬더니 적당한 시간에 통과를 했다.
사실상 거창한 방법들이 사용된 것은 아니고 구현 하는데 시간이 오래걸리는 문제였고, 자료를 어떤식으로 표현하는지가 중요했던 것 같다.
[소스 코드]
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>
#define pii pair<int,int>
#define pip pair<int,pii>
using namespace std;
int N, M, K;
int dx[8] = { -1, 0 ,1,-1,1,-1,0,1 };
int dy[8] = { -1,-1,-1,0,0,1,1,1 };
vector<vector<int>> food;
vector<vector<int>> mp;
vector<int> Tree[11][11];
queue<pip> dead_tree;
queue<pii> production;
void spring()
{
//나무의 나이만큼 양분을 먹음
//한 칸에 여러개의 나무가 있다면 어린나무 부터 먹음
//나이만큼 양분을 먹을 수 없다면 죽음
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (Tree[i][j].size() == 0) continue;
sort(Tree[i][j].begin(), Tree[i][j].end());
vector<int> tmp;
for (int k = 0; k < Tree[i][j].size(); k++)
{
if (mp[i][j] < Tree[i][j][k])
{
dead_tree.push({ Tree[i][j][k],{i,j} });
}
else
{
mp[i][j] = mp[i][j] - Tree[i][j][k];
if ((Tree[i][j][k] + 1) % 5 == 0)
{
production.push({ i,j });
}
Tree[i][j][k]++;
tmp.push_back(Tree[i][j][k]);
}
}
Tree[i][j].clear();
for (int h = 0; h < tmp.size(); h++) Tree[i][j].push_back(tmp[h]);
}
}
}
void summer()
{
//죽은 나무들이 그 자리에 나이/2 만큼 양분을 생성
while (!dead_tree.empty())
{
pip tmp = dead_tree.front(); dead_tree.pop();
mp[tmp.second.first][tmp.second.second] += tmp.first / 2;
}
}
void autumn()
{
//번식을 하는 나무는 5의배수
//주변 8칸에 번식을함 -> 생기는 나무는 나이가 1 짜리
while (!production.empty())
{
pii tmp = production.front(); production.pop();
for (int i = 0; i < 8; i++)
{
int nx = tmp.second + dx[i];
int ny = tmp.first + dy[i];
if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
Tree[ny][nx].push_back(1);
}
}
}
void winter()
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
mp[i][j] += food[i][j];
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
mp.resize(N + 1);
food.resize(N + 1);
for (int i = 0; i < N + 1; i++) { mp[i].resize(N + 1); food[i].resize(N + 1); }
for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { cin >> food[i][j]; mp[i][j] = 5; }
int y, x, age;
for (int i = 0; i < M; i++)
{
cin >> y >> x >> age;
Tree[y][x].push_back(age);
}
for (int i = 0; i < K; i++)
{
spring();
summer();
autumn();
winter();
}
int sum = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
sum += Tree[i][j].size();
}
}
cout << sum;
}
굳