문제
https://www.acmicpc.net/problem/16235
리뷰
문제 유형: 구현, 시뮬레이션, 자료구조
격자를 이용하지만 그래프 탐색을 이용하지는 않는다.
문제를 천천히 이해하다보면, 계절에 따른 시퀀스만 잘 구현하면 된다는 것을 어렵지 않게 파악할 수 있다.
주의해야할 점은, Spring → Summer로 넘어가는 시점에서 나무의 나이 > 양분 일 경우 죽는 나무를 파악하기 위한 과정에서 반복문의 조건을 건드리게 되는 경우가 발생할 수 있다.
// 예시
for(int i=0; i<vectorB.size(); i+){
if(나무의 나이 > 양분)
vectorB[i].erase ....
else
....
}
// answer
...
vectorB.clear()
vectorB = vectorC위와 같이 vector B에 대해 반복하는 for 문 내에서 vector B를 erase하면 사이즈가 줄어든다. 그렇다고 사이즈를 미리 저장해두자니 index에러가 난다. 이 경우, 모든 연산이 끝난 후, 새로운 벡터를 만들어 놓고, 남겨두고자 하는 원소들을 따로 저장해두고 vector B = vector C 와 같이 재 할당해주는 방법이 대안이 될 수 있다,
또한, '어린'나무를 먼저 키우기 위한 방법으로 sort를 사용할 수도 있으나, 시간복잡도를 고려한다면 sort 대신 문제의 특성상 나무를 저장하는 벡터 앞에 insert하는 것도 방법이 될 수 있다는 것을 알 수 있다(내부적으로 insert를 진행하면 시간복잡도는 O(N)이지만, Sort하면 빨라야 O(NlogN)이다. 나무의 개수가 적으면... sort가 더 빠를 수 있다만 글쎄?)
구현을 위해 전체 반복을 진행하고 있으므로, 전체 반복문에 대한 종료조건설정도 하나의 관문이다.
실수한 부분
- 3차원 벡터를 처음 사용하려고 하다보니 구글링이 필요했다. raw한 3차원 벡터보다는 아래와 같은 방식이 편하다.\
// too raw
vector<vector<vector<int>>> map(SIZE, vector<vector<int>>(SIZE, vector<int)());
// better and easier
vector<int> map[SIZE][SIZE];- 전체 반복문을 동작시킬 때는 반복문 시작할 때마다 무엇인가가 중복되지 않도록 RESET해주어야 한다. deadtree를 저장하는 vector를 초기화하지 않아 값이 누적되었다.
- 3차원 벡터를 전체 서치하려고 하는 과정에서 시간복잡도가 추가되었다(3중 for문)
양분을 먹지 못해 죽는 나무들은 최종적으로 해당 벡터에서 제거함으로써 2중 for문으로 줄여야 했다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K;
int A[11][11];
int energy[11][11];
vector<int> tree[11][11];
vector<int> afterspring[11][11];
vector<int> deadtree[11][11];
bool InRange(int x, int y){
return ( x<1 || x>N || y<1 || y>N ) ? false:true;
}
void Spring(){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(tree[i][j].size()!=0)
sort(tree[i][j].begin(), tree[i][j].end());
for(int k=0; k<tree[i][j].size(); k++){
int age = tree[i][j][k];
int en = energy[i][j];
if(en >= age){
afterspring[i][j].push_back(age+1); // for문을 안건드리도록 벡터를 추가했다.
energy[i][j] -= age;
}
else if(age!= -1 && en < age){
//tree[i][j].erase(tree[i][j].begin()+k); // 이 구문이 k에 해당하는 for문을 건드린다.
deadtree[i][j].push_back(age);
}
}
tree[i][j].clear();
tree[i][j] = afterspring[i][j];
afterspring[i][j].clear();
}
}
}
void Summer(){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
for(int k=0; k<deadtree[i][j].size(); k++){
int dage = deadtree[i][j][k];
int de = dage/2;
energy[i][j] += de;
}
deadtree[i][j].clear(); // 이걸 안해줘서 계속 누적되었다.
}
}
}
void Fall(){
int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
for(int k=0; k<tree[i][j].size(); k++){
int age = tree[i][j][k];
if(age%5 == 0){
for(int d=0; d<8; d++){
int ni = i + dir[d][0];
int nj = j + dir[d][1];
if(InRange(ni, nj)){
//tree[ni][nj].insert(tree[ni][nj].begin(), 1);
tree[ni][nj].push_back(1);
}
}
}
}
}
}
}
void Winter(){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
int en= A[i][j];
energy[i][j] += en;
}
}
}
void Print(){
cout << '\n';
for(int i=1; i<11; i++){
for(int j=1; j<11; j++)
cout << tree[i][j].size() << " ";
cout << '\n';
}
cout << '\n';
}
int Solve(){
int year = 0;
// init
cin >> N >> M >> K;
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
cin >> A[i][j];
energy[i][j] = 5;
}
}
for(int t=0; t<M; t++){
int x, y, age;
cin >> x >> y >> age;
tree[x][y].push_back(age);
}
//Print();
// loop
while(year < K){
Spring(); //Print();
Summer(); //Print();
Fall(); //Print();
Winter(); //Print();
year ++;
}
// print
int answer=0;
for(int i=1; i<11; i++){
for(int j=1; j<11; j++){
answer += tree[i][j].size();
}
}
return answer;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int answer = Solve();
cout << answer;
return 0;
}