[백준 16235번] 나무재테크 - C++ (삼성sw역량테스트 기출)

 

나무재테크 문제는 삼성SW역량테스트 기출문제로, 난이도 Gold4의 시뮬레이션 문제였습니다.

(문제출처 :  https://www.acmicpc.net/problem/16235 )

 

일단, 문제를 읽으면서 필요한 변수를 생각해봅시다. 개요부분과 주 내용, 두 부분으로 나눠서 살펴볼게요. 

1.

입력받은 값에 따라 땅의 크기가 정해집니다. 하지만 N의 최댓값이 크지 않다면 동적할당으로 하나씩 할당하지 않고, 처음부터 최댓값만큼의 크기로 배열을 선언합니다.

 

2.

r,c가 1부터 시작하므로 각각 1~N까지의 값을 가집니다. 따라서 위에서 말한 이차원 배열의 크기 [11][11] 로 했습니다.

 

3. 땅을 표현할 이차원배열이 필요합니다. 전부 5로 초기화합니다. → int ground[11][11];

 

4. 같은 칸에 여러 개의 나무가 심어질 수도 있다는 걸로 보아 각 칸 별로 나무를 저장해야 할 것 같습니다. 즉, 땅 좌표의  각 한 칸마다 그 칸에 심어진 나무들을 벡터로 저장할 겁니다.

→ vector<int>map[11][11]; map[r][c].push_back(나무정보);

 

 

봄)

- 각 칸에 있는 여러 나무들이 나이가 어린 순으로 그 칸의 양분을 먹음

- 양분을 먹을 땐 자신의 나이만큼 먹고, 나이가 1 증가 / 그 칸의 양분이 자기 나이보다 적으면 양분을 먹지 못하므로 즉시 죽음

 

여름) 

- 죽은 나무 각각의 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가됨 → 죽은 나무를 저장할 벡터 필요

 

가을)

- 나무 나이가 5의 배수일 때 인접한 8개 칸에 1살짜리 나무가 생김 →

 

BFS에서 주로 쓰이는 방식처럼, for문과 배열을 이용해서 행과 열을 한번에 이동시켜 8개 칸에 모두 접근하자.

이동방향을 담은 배열 dx[8]는 행 이동을 위한(r값 변경을 위한) 배열, dy[8]는 열 이동을 위한(c값 변경을 위한) 배열이다.

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

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

 

겨울)

- 입력받은 배열의 값이 매년 땅 양분에 더해지기 때문에, 땅을 표현한 이차원 배열과 매년 더해질 값을 저장한 이차원 배열을 구분해서 만들어 줍니다. → int a[11][11]; 

 

k년 동안 사계절을 반복한다고 했으니, 각 계절별 함수를 만들어 네 함수를 반복하면 됩니다.

이제 전체 코드를 보면서 하나씩 짚어봅시다.

 

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

vector<int>map[11][11];			//각 좌표별 심어진 나무를 벡터로 저장할 예정
int a[11][11] = { 0, };			//매년 더해질 양분 ( 입력으로 값 받음)
int ground[11][11] = { 0, };		//땅의 현재 남은 양분을 저장할 배열
struct tree { int x, y, age; };		//죽은 나무벡터를 위한 구조체
int n, m, k;				//땅 크기, 나무개수, k년
vector<tree>dead;			//죽은 나무 벡터

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

void input();
void spring();
void summer();
void fall();
void winter();

void input() {
	cin >> n >> m >> k;
	//맨 처음 땅 양분은 모두 5
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			ground[r][c] = 5;
		}
	}
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			cin >> a[r][c];
		}
	}
	//m개 나무 입력
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		map[x][y].push_back(z);//z는 age
	}
}

void spring() {
	//나이어린순 나무 정렬
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			sort(map[r][c].begin(), map[r][c].end());
		}
	}
	//각 칸별로 양분 먹는 나무와 죽는 나무 확인
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			for (int i = 0; i < map[r][c].size(); i++) {
				if (ground[r][c] >= map[r][c][i]) {//양분먹기가능
					ground[r][c] = ground[r][c] - map[r][c][i];//양분먹고
					map[r][c][i]++;//나이 1증가
				}
				else {//양분 못먹음
					dead.push_back({ r,c,map[r][c][i] });
					map[r][c].erase(map[r][c].begin() + i);//죽음
					i--;//vector.erase에 성질에 따라 i인덱스 줄여야 함
				}
			}
		}
	}
}

void summer() {
	for (int i = dead.size() - 1; i >= 0; i--) {
		int r = dead[i].x;
		int c = dead[i].y;
		ground[r][c] = ground[r][c] + dead[i].age / 2;
	}
	dead.clear(); dead.resize(0);//매 해 죽는 나무 업데이트를 위해
}

void fall() {
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			for (int i = 0; i < map[r][c].size(); i++) {
				if (map[r][c][i] % 5 == 0 && map[r][c][i] >= 5) {
					for (int j = 0; j < 8; j++) {
						int nx = r + dx[j];
						int ny = c + dy[j];
						if (1 <= nx && nx <= n && 1 <= ny && ny <= n) {
							map[nx][ny].push_back(1);
						}
					}
				}
			}
		}
	}
}

void winter() {
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			ground[r][c] = ground[r][c] + a[r][c];
		}
	}
}

int main() {
	input();
	while (k > 0) {
		k--;
		spring();
		summer();
		fall();
		winter();
	}
	int answer = 0;
	for (int r = 1; r <= n; r++) {
		for (int c = 1; c <= n; c++) {
			answer = answer + map[r][c].size();
		}
	}
	cout << answer;
	return 0;
}

 

spring()에서는 땅에 남은 양분이 자신의 나이보다 적어서 양분을 먹지 못하고 바로 죽는 경우, dead라는 vector로 죽은 나무의 정보를 저장하고, 기존 벡터에서 이 나무를 삭제합니다.

 

제가 가장 실수가 많았던 곳은 죽은 나무를 벡터에서 삭제하는 부분이었어요.

vector의 중간요소 삭제는 erase()로 구현했습니다.

erase()는 벡터에서 특정 위치의 요소를 제거하고, 제거된 만큼 크기가 줄어드는 메소드입니다.

 

map[r][c].erase(map[r][c].begin()+i);

i--;

 

vector.begin()과 vector.end()는 Iterator(반복자), 즉 포인터와 비슷한 개념으로 요소들의 위치와 관련된 객체를 반환합니다. begin()은 맨 앞 요소 앞의 벡터 시작점을, end()는 맨 끝 요소 뒤의 벡터 끝 점을 가리킵니다. i번째 인덱스에 있는 값을 삭제할 땐 vector.erase(vector.begin()+i);로 하면 됩니다.

 

단, 여기서 주의할 점이 erase를 하고 나면 인덱스가 한 칸씩 앞으로 밀린다는 점입니다.

따라서 i값을 증가시켜 for문을 진행시키기 전에, i--;를 통해 i값을 줄여야 합니다.

STL을 이제 막 공부하기 시작한 저는 여기서의 실수로 인해 몇 번이고 다시 풀었네요......

기초가 왜 중요한 지 또 한번 깨닫는 하루입니다...^^;;

 

왜 i값을 줄여야 하는 지 이해가 어려우신 분들은 아래 링크를 통해 자세한 설명을 참고해주세요!

참고 : 벡터의 i번째 요소(중간요소) '실수 없이' 삭제하기

https://eocoding.tistory.com/3?category=918066

 

summer()은  매년 봄에 죽는 나무가 달라지니까 dead.clear(); dead.resize(0);을 통해 계속 초기상태로 나무벡터를 돌려줍니다. 양분이 된 나무는 죽은 나무 벡터에 정보를 남길 필요가 없으니까요. 참고로, clear는 요소만 없애줄 뿐 메모리가 그대로이기 때문에, resize를 하지 않으면 나중에 잘못된 인덱스 접근이 일어날 수 있으니 주의해야 합니다.

 

fall()은 번식의 계절입니다. 이 부분도 실수할만한 부분을 짚자면,(제가 했습니다..ㅎㅎ) 5의 배수 조건입니다.

5의 배수는 5로 나눈 값이 0임을 확인해도 좋지만 저처럼 %연산자로 나머지를 확인하실 거라면 5보다 작은 수는 포함되지 않도록 해야 합니다.

 

winter()은 비교적 간단하게, 처음에 입력받은 a배열을 매 년 겨울에 땅 양분에 더해주면 끝이에요.

 

마지막으로, while문을 통해 k년동안 사계절을 반복하고 k년 후에 모든 map을 탐색하면서 벡터 요소들(나무들)의 개수를 세면 됩니다.

 

수정해야 할 내용, 이해가 어려운 내용이 있으시면 댓글로 남겨주세요. :-)

 

초보의개인적인 생각들 : 

1. '땅 양분말고도 나무의 양분을 변수로 선언해야 하나?' 라는 고민을 했다. 하지만 양분은 자기 나이만큼 먹으므로 나이 변수를 사용하면 되고, 나무 각각의 현재 양분에 대한 연산은 없으므로 현재 먹은 양분에 대한 변수를 만들 필요는 없다.

 

2. 시뮬레이션은 문제가 길어서 한번에 함수들 다 짜고 나서 오류 확인하는 게 어렵다. 처음부터 테스트 해 가면서 진행하도록 하고 기초를 탄탄히 해야겠다.....