[16235]나무 재테크(C++/구현)

1. 문제

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

2. 접근 방법

 

1. 특별한 알고리즘을 써야 한다기 보단 구현 문제이다. 구현일 수록 사용할 자료구조 선택, index 의미에 유의하자!

 

 2. 문제의 조건 & 제약 사항을 파악하자 (다음은 문제를 읽으면서 생각한 흐름)

    1) 한 칸에 "여러 개"의 나무가 있을 수 있다. => "container형 이차원 배열 사용해야 겠다."

 

    2) 양분을 먹을 때, 나이가 어린 나무부터 먹는다. => "정렬이 필요하겠다. container 중 multi_set을 써도 될 것 같다."

 

    3) 양분을 먹고 난 나무는 나이가 1씩 증가한다 => "container값이 업데이트 되는구나" => "container 중 값 수정이 용이한 걸 써야 겠다. " => "set,queue는 쓰면 안되겠다. vector를 사용하자.(자료구조 선택)"

 

    4) 양분을 먹지 못하는 나무는 죽고, 양분이 된다. => "죽은 나무들을 따로 저장해야 나중에 양분으로 더할 수 있겠다." 

 

    5)그 외 가을 & 겨울은 따로 생각할 것 안보임 => 이제 예제를 파악하면서 구현..

 

* 참고 : container관련 정리 글

https://m.blog.naver.com/PostView.nhn?blogId=jidon333&logNo=60212565975&proxyReferer=https:%2F%2Fwww.google.com%2F

STL : 컨테이너 ( Container )

 

3. 조심 할 것 & 새로 안 부분 

 

1. 벡터(배열) 내 "값"만 알면 될 때 auto쓰자.

아래 예처럼 iterator나 index로 접근해야 할 때는 원래 방식대로 쓰자.

    1 ) erase(), copy() 등 매개변수가 iterator형인 함수를 호출 할 때

     2) 벡터 값과 특정 위치의 값과 비교해야 할 때(ex. v[i]와 map[i][j]값을 비교해야 할때, i가 정해질 때)

 

 

2. 런타임 에러 발생시 확인 루틴 ( 내가 주로 실수하는 부분부터 확인하기)

    1) for문 범위 check

    2)  v.empty()  확인해야 하는 곳 있는지 check

    3) 메모리 할당 안되었는데 값 넣었는지 check ,(+ 해제된 메모리 다시 참조 할 때 empty확인 여부 안하고 접근했는지,메모리 할당 했는지 확인)

    4) iterator check(특히 erase함수 조심, 가리키는 값의 의미 확인)

    5) copy함수 check(메모리 선언 안해놓고, 혹은 resize안하고 copy했는지 확인!!!)

    6) 그래도 못찾겠다 => 의심되는 함수(구간) 주석 처리 해보기. 틀렸습니다 나왔으면 어쨌든 런타임에러는 안난다는 소리이므로 그 부분 수정하기 

(*) 런타임 에러 발생 원인

1. 배열에 할당된 크기를 넘어서 접근했을 때
2. 전역 배열의 크기가 메모리 제한을 초과할 때
3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
4. 0으로 나눌 때
5. 라이브러리에서 예외를 발생시켰을 때
6. 재귀 호출이 너무 깊어질 때
7. 이미 해제된 메모리를 또 참조할 때
8. 반환형이 void가 아닌 함수에서 아무런 값을 반환하지 않았을 때

=> 주로  배열 인덱스 범위, 잘못된 공간에 접근하는 경우, 0으로 나누는 경우 때문에 발생

 

 

3. fill 함수에 대하여

   1) 사용 법 : fill(시작 주소, 끝주소+1, 채울 값)

   2) 함수의 매개변수 : iterator(v.begin()) , 주소값(&arr[0])으로 표현함

   3) 2차원 배열의 fill 함수 사용 : fill(&arr[0][0], &arr[MAX-1][MAX], value); //2차원 배열 end값 조심하기!!

    4) 벡터 형 2차원 배열에 메모리 할당 및 초기화: fill(&arr[0][0],&arr[MAX-1][MAX], vector<int>(N,value));

   (코테 할 때 써먹기)

   5) fill_n함수 : fill_n(변경하려는 원소의 범위 시작주소, 변경하려는 원소 갯수, 변경 값)

   6) fill 함수도 사용하기 전에 크기만큼 메모리 할당 해야함

 

 

4. "앞으로는 이거때문에 고민하느라 시간낭비 하지 말자" 모음

   1) int arr[3] = {1,} = {1,0,0}; //1,1,1 아님! 일부만 지정하는 경우 나머지는 모두 0으로 채워짐

 

   2) distance(iterator_begin, iterator_end) : [begin~end)크기를 반환하는 함수

    => 특정 iter와 v.begin() 혹은 v.end()사이 요소 개수 구할때 사용하기 좋음

 

   3) 2차원 벡터에 들어있는 요소 개수를 한번에 구할 수 없을 까?

    => (아직까지 내가 찾아본 바로는 없음. 고민하지 말고) 행 단위로 sum += v[i].size(); 구하자.

 

   4) v.clear() : 원소가 제거되는 것(size = 0), 메모리는 할당된 상태임(capacity = 4)

   

 

5. vector 과 set 차이 

   1) vector을 사용하기 좋을 때

        - 중간 삽입, 삭제가 없음

        - 랜덤 접근을 자주 함(index 접근)

        - 값 수정이 가능해야 함

 

   2) set을 사용하기 좋을 때

       - 값 수정이 없음

       - 랜덤 접근이 없음(index 접근)

       - 탐색을 자주 함

       - 자동 정렬이 필요함

 

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 11
#define FOR(i,n) for(int i =1;i<=n;i++)

using namespace std;
int N;
int A[MAX][MAX]; //겨울마다 제공되는 양분 
vector<int> trees[MAX][MAX];
pair<int, int > dir[8] = { {-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,-1},{1,1} };

int go(int K) {
	vector<int> die[MAX][MAX];	//죽은 나무들 
	int food[MAX][MAX];  //현재 양분
	FOR(i, N)
		fill(food[i], food[i] + MAX, 5);
	while (K--) {
		//봄 : 양분 & 나이 먹기  
		FOR(i, N) {
			FOR(j, N) {
				if (trees[i][j].empty()) continue;
				sort(trees[i][j].begin(), trees[i][j].end());

				int& fd = food[i][j]; // (i,j)의 현재 양분
				for (auto it = trees[i][j].begin(); it != trees[i][j].end(); it++) {
					if (*it > fd) {
						die[i][j].resize((int)distance(it, trees[i][j].end())); //die벡터에 메모리 할당 후, 죽은 나무들 복사
						copy(it, trees[i][j].end(), die[i][j].begin());
						trees[i][j].erase(it, trees[i][j].end());//erase 함수 
						break;
					}
					fd -= *it;
					(*it)++;
				}
			}
		}

		//여름 : 죽은 나무들의 나이/2만큼 양분에 추가 
		FOR(i, N) {
			FOR(j, N) {
				if (die[i][j].empty()) continue;
				for (auto x : die[i][j]) {
					food[i][j] += x / 2;
				}
				die[i][j].clear();
			}
		}

		//가을 : 나무의 확장 
		FOR(i, N) {
			FOR(j, N) {
				for (auto x : trees[i][j]) {
					if (x % 5 == 0) {
						for (int k = 0; k < 8; k++) {
							int ni = i + dir[k].first;
							int nj = j + dir[k].second;
							if (ni <= 0 || nj <= 0 || ni > N || nj > N) continue;
							trees[ni][nj].push_back(1);
						}
					}
				}
			}
		}

		//겨울 : 양분 제공
		FOR(i, N) {
			FOR(j, N)
				food[i][j] += A[i][j];
		}
	}

	//살아 남은 나무 수 찾기
	int sum = 0;
	FOR(i, N) {
		FOR(j, N) {
			if (trees[i][j].empty()) continue;
			sum += trees[i][j].size();
		}
	}
	return sum;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int M, K;
	cin >> N >> M >> K;
	//양분 배열 입력 받음
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++)
			cin >> A[i][j];
	}

	//각 나무 정보 입력 받음 
	for (int i = 1; i <= M; i++) {
		int r, c, old;
		cin >> r >> c >> old;
		trees[r][c].push_back(old);
	}

	cout << go(K) << endl;

	return 0;
}