[백준/BOJ] 16235번 나무 재테크 (C++)

www.acmicpc.net/problem/16235

16235번: 나무 재테크

삼성 역량 테스트 기출 문제 : 시뮬레이션(구현) (다시 풀기)

 

입력 조건

• N : map의 가로, 세로 크기
• M : 구매하여 심은 나무의 수
• K : 지난 시간
• x, y : 나무의 위치, z : 나무의 나이

제한 사항

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
• 입력으로 주어지는 나무의 위치는 모두 서로 다름

문제 요약

• 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
• 봄
  • 자신의 나이만큼 양분을 먹고, 나이가 1 증가 \
  • 각각의 나무는 나무가 있는 1x1 크기의 칸에 있는 양분만 먹을 수 있음
  • 하나의 칸에 여러개의 나무가 있다면, 어린 나무부터 양분을 먹음 땅에 양분이 부족, 자신의 나이만큼 양분을 먹을 수 없는 경우 => 나무가 죽음
• 여름
  • 죽은 나무 => 양분
  • 각각의 죽은 나무의 나이 / 2 => 양분으로 추가 (소수점 아래는 버림)
• 가을
  • 나무가 번식하며, 나무의 나이가 5의 배수여야 함
  • 인접한 8개의 칸에 나이가 1인 나무가 생김 (map의 범위를 벗어나는 칸은 나무 생성 x)
• 겨울
  • 전체 map의 양분을 추가
  • 추가하는 양분의 양은 초기에 받은 A[r][c]

문제의 조건이 많아서 위와 같이 정리를 한 후 문제에 접근했습니다. 조건에 맞게 구현만 하면 되는 문제라 굉장히 쉽게 느껴졌는데, 알고보니 시간 제한이 0.3초로 굉장히 타이트한 문제였습니다. 처음에 리스트를 이용해서 봄, 여름, 가을, 겨울에서 일어나는 각각의 이벤트들을 구현했는데 계속해서 시간초과가 발생했습니다.

 

/* 시간초과 발생, 최적화 필요 */ 

#include <iostream>
#include <list>
using namespace std;

struct Tree {
	int x, y, age;
	bool isAlive;
};

int N, M, K;
int A[11][11], F[11][11]; // A : 겨울에 추가될 양분의 양, F : 땅의 양분의 양
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
list<Tree> tree; // 심어진 나무의 좌표, 나이, 상태를 저장하는 리스트

void spring() { // 봄의 이벤트
	for(list<Tree>::iterator it = tree.begin(); it != tree.end(); it++) {
		if(it -> age <= F[it -> x][it -> y]) {
			F[it -> x][it -> y] -= it -> age;
			it -> age++;
		} else it -> isAlive = false;
	}
}

void summer() { // 여름의 이벤트
	for(list<Tree>::iterator it = tree.begin(); it != tree.end(); ) {
		if(!(it -> isAlive)) {
			F[it -> x][it -> y] += it -> age / 2;
			it = tree.erase(it);
		} else it++;
	}
}

void autumn() { // 가을의 이벤트
	for(list<Tree>::iterator it = tree.begin(); it != tree.end(); it++) {
		if(it -> age % 5 == 0) {
			int x = it -> x;
			int y = it -> y;
			for(int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
				tree.push_front({ nx, ny, 1, true });
			}
		}	
	}
}

void winter() { // 겨울의 이벤트
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= N; j++) {
			F[i][j] += A[i][j];
		}
	}
}

int makeMoney() { // 나무 재테크 시작
	while(K--) {
		spring();
		summer();
		autumn();
		winter();
	}
	
	return tree.size(); // 남아있는(살아있는) 나무의 수 리턴
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int x, y, z;
    cin >> N >> M >> K;
    
    for(int i = 1; i <= N; i++) {
    	for(int j = 1; j <= N; j++) {
    		cin >> A[i][j];
    		F[i][j] = 5;
		}
	}
	
	for(int i = 0; i < M; i++) {
		cin >> x >> y >> z;
		tree.push_back({ x, y, z, true });
	}
	
    cout << makeMoney();
}

 

시간초과가 발생한 원인은 크게 두가지로 나뉘는 것 같았습니다.

 

1. 봄의 이벤트에서 죽게 되는 나무가 결정되고, 여름 이벤트에서 죽은 나무들을 제거하고 양분으로 만들어 추가하는 작업을 하는데, 이 과정에서 O(N)의 작업이 두번 일어나기 때문에 시간 낭비가 발생합니다. 따라서 봄에 죽게 되는 나무가 결정됐을 때, 여름의 작업을 한꺼번에 하여 시간복잡도를 줄이려고 시도했습니다. (즉 봄과 여름의 이벤트를 합쳐서 구현했습니다.)

 

2. 문제 중간에 erase를 하고 push_front를 해야해서 list를 썼었는데, 이게 잘못된 판단이었던 것 같습니다. STL list는 cache hit 문제로 인해 실행속도가 vector, deque에 비해 심각하게 느리다고 합니다. (참고글)

이러한 문제를 해결하기 위해서, vector를 사용하였고, 죽은 나무를 삭제하는 작업은 실제로 erase를 사용하지 않고, 벡터를 하나 선언해 살아남는 나무를 저장해 똑같은 기능을 하게끔 구현했습니다. 이렇게 하면 삭제 작업을 하지 않아도 삭제된 것처럼 처리할 수 있으므로 list를 사용할 필요가 없어집니다. 

그리고 가을에도 벡터를 사용해서 새로 번식되는 나무들을 저장하게끔 구현하였고, 이를 copy 함수를 이용해 새로 번식된 나무들이 저장된 벡터가 앞에 올 수 있게끔 하여 list를 사용하지 않더라도 push_front와 같은 효과를 내게끔 구현했습니다.

 

/* 최적화 완료 */

#include <iostream>
#include <vector>
using namespace std;

struct Tree {
	int x, y, age;
};

int N, M, K;
int A[11][11], F[11][11]; // A : 겨울에 추가될 양분의 양, F : 땅의 양분의 양
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
vector<Tree> tree; // 심어진 나무의 좌표, 나이, 상태를 저장하는 벡터  

void spring_summer() { // 봄과 여름의 이벤트
	int newAdd[11][11] = {}; // 죽은 나무가 양분이 될 때 그 값을 저장할 배열 
	vector<Tree> newTree; // 살아남는 나무가 저장될 벡터 
	
	for(auto it = tree.begin(); it != tree.end(); it++) {
		if(it -> age <= F[it -> x][it -> y]) {
			F[it -> x][it -> y] -= it -> age;
			it -> age++;
			newTree.push_back(*it);
		} else newAdd[it -> x][it -> y] += it -> age / 2; 
	}
	
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= N; j++) {
			F[i][j] += newAdd[i][j];
		}
	}
	
	tree = newTree;
}

void autumn() { // 가을의 이벤트
	vector<Tree> newTree; // 새로 번식되는 나무들이 저장될 벡터 
	for(auto it = tree.begin(); it != tree.end(); it++) {
		if(it -> age % 5 == 0) {
			int x = it -> x;
			int y = it -> y;
			for(int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
				newTree.push_back({ nx, ny, 1 }); 
			}
		}	
	}
	
	copy(tree.begin(), tree.end(), back_inserter(newTree)); // newTree 뒤에 tree를 copy한다.
	tree = newTree;
}

void winter() { // 겨울의 이벤트
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= N; j++) {
			F[i][j] += A[i][j];
		}
	}
}

int makeMoney() { // 나무 재테크 시작
	while(K--) {
		spring_summer();
		autumn();
		winter();
	}
	
	return tree.size(); // 남아있는(살아있는) 나무의 수 리턴
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int x, y, z;
    cin >> N >> M >> K;
    
    for(int i = 1; i <= N; i++) { 
    	for(int j = 1; j <= N; j++) {
    		cin >> A[i][j];
    		F[i][j] = 5;
		}
	}
	
	for(int i = 0; i < M; i++) {
		cin >> x >> y >> z;
		tree.push_back({ x, y, z });
	}
	
    cout << makeMoney();
}