문제

안녕하세요.
백준에서 삼성 SW 역량 테스트 기출 문제집에 게시된 16235번 나무재테크 문제 풀이를 소개하겠습니다.

이번 문제는 2차원 배열 내에서 여러 나무를 심고, 영양분을 공급하며, 나무가 다시 번식하고 죽는것에 따라 남은 나무의 수가 몇개인지를 물어보고 있습니다.

많은 분들이 아시겠지만, 이렇게 특정 작업을 일정 횟수만큼 진행 시키는 문제들을 시뮬레이션 문제라고 부릅니다.

따라서 인덱스 체크와 조건 처리만 실수 없이 잘 해준다면 풀 수 있는 문제입니다.

풀이 코드는 사람이 쉽게 이해 할 수 있는 코드를 지향하여 작성하였습니다. 따라서 최적의 성능을 가지는 코드가 아닐 수 있습니다.

주어진 정보

  • 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
  • 봄에 나이만큼 양분을먹고, 나이가 1 증가.
    • 칸에 여러 나무가 있다면, 나이가 어린순으로 양분 섭취.
  • 여름에는 양분을 먹지 못한 나무가 사망 후, (나이/2) 만큼 양분으로 변환.
  • 가을에는 나무의 나이가 5의 배수라면, 인접한 8개의 칸에 나이가 1인 나무 번식.
  • 겨울에는 처음 주어진 배열 A 만큼 양분 추가.
  • N : 땅의 크기
  • M : 처음 주어지는 나무의 갯수
  • K : 결과를 확인하는 년 수, 반복 실행하는 횟수

해결 방향

계산이 꼬이지 않게(실수를 방지하기 위해), 문제에서 주어진 계절마다의 작업들을 함수로 만들어 K 년 수 만큼 반복을 진행합니다.

풀이

풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector < vector < vector <int> > > arr_tree;	// 각 위치에 있는 나무들의 나이 정보
vector < vector < vector <int> > > arr_dead;	// 각 위치에 있는 죽은 나무들의 나이 정보
vector < vector < int > > arr_n;				// 각 위치에 있는 영양분의 정보
vector < vector < int > > A;					// 각 위치에 로봇이 공급할 영양분의 정보

int N, M, K;	//N : 땅의 크기, M : 초기 나무 갯수, K : 시뮬레이션 횟수
int dd[][8] = {
	{-1,-1,0,1,1,1,0,-1},
	{0,1,1,1,0,-1,-1,-1}
};


// 땅 경계 체크
bool check_boundary(int r, int c) {
	if (r < 0 || r >= N) return false;
	if (c < 0 || c >= N) return false;

	return true;
}

// 인접한 여덟 방향에 나무 추가
void add_new_tree(int r, int c) {
	for (int way = 0; way < 8; way++){
		int r_ = r + dd[0][way];
		int c_ = c + dd[1][way];

		// 경계를 벗어나면 패스
		if (check_boundary(r_, c_) == false) continue;

		// 맨 앞에 나이가 1인 나무 추가
		arr_tree[r_][c_].insert(arr_tree[r_][c_].begin(), 1);
	}
}

//나무를 나이 순으로 정렬
void sorting_trees() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (arr_tree[r][c].size() > 1) {
				sort(arr_tree[r][c].begin(), arr_tree[r][c].end());
			}
		}
	}
}

// 모든 나무들이 영양분을 섭취하고 나이 1 증가
void spring() {

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {

			// 해당 위치에 나무의 수 만큼 영양분 섭취
			for (int i = 0; i < arr_tree[r][c].size(); i++) {

				// 영양분이 충분하지 않다면 해당 나무 위치부터 끝까지 사망 처리 (나이순 정렬 된 조건)
				if (arr_tree[r][c][i] > arr_n[r][c]) {
					arr_dead[r][c] = vector<int>(arr_tree[r][c].begin() + i, arr_tree[r][c].end());	// 죽어야 할 나무들의 정보 복사
					arr_tree[r][c].erase(arr_tree[r][c].begin() + i, arr_tree[r][c].end());			// 땅에서 나무들 제거
					break;
				}

				// 영양분 공급
				arr_n[r][c] -= arr_tree[r][c][i];
				arr_tree[r][c][i]++;	// 입력으로 주어지는 나무의 나이는 10이하지만, 실행 중의 나이제한의 언급은 X
			}
		}
	}

}

// 양분 섭취를 못한 나무들이 (나이/2)만큼 양분으로 변환 됨
void summer() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {

			// 모든 나무들에 대해 처리, 없으면 다음 위치 진행
			while(arr_dead[r][c].size() > 0) {
				arr_n[r][c] += int(arr_dead[r][c].front() / 2);	// 맨 앞의 나무부터 계산
				arr_dead[r][c].erase(arr_dead[r][c].begin());	// 계산된 맨 앞 나무 제거
			}
		}
	}
}

// 땅에 위치한 나무의 나이가 5의 배수라면, 인접한 8개의 칸에 나이가 1인 나무 번식.
void fall() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			
			// 살아있는 모든 나무들에 대해 5의 배수 체크
			for (auto age : arr_tree[r][c]) {
				if (age % 5 == 0) {
					add_new_tree(r,c);
				}
			}
		}
	}
}

// 로봇이 땅에 양분 추가
void winter() {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			arr_n[r][c] += A[r][c];
		}
	}
}

// 모든 땅의 나무의 수를 계산하여 반환
int get_total_tree() {
	int total = 0;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			// 모든 땅의 나무의 수를 계산
			total += arr_tree[r][c].size();
		}
	}

	return total;
}

int solution() {

	while (K > 0) {
		// 해당 년도의 사망 할 나무를 저장할 배열 초기화
		arr_dead = vector < vector < vector <int> > >(N, vector < vector <int> >(N, vector<int>()));

		// 봄
		//1 ≤ N ≤ 10 이기 때문에 충분히 전체 탐색 할만함.
		spring();
		summer();
		fall();
		winter();

		sorting_trees();
		K--; // 실행 횟수 감소
	}

	return get_total_tree();
}

int main() {
	cin >> N >> M >> K;

	arr_tree = vector < vector < vector <int> > >(N, vector < vector <int> > (N, vector<int>()));
	arr_n = vector < vector <int> >(N, vector<int>(N, 5));	// 모든 땅에는 처음에 5만큼의 양분이 존재
	A = vector < vector <int> >(N, vector<int>(N, 0));

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> A[r][c];
		}
	}

	for (int m = 0; m < M; m++) {
		int r, c, age;
		cin >> r >> c >> age;
		arr_tree[r-1][c-1].push_back(age);	// 항상 나이 순으로 주어질까?
	}
	sorting_trees(); // 입력 받은 나무들을 나이 순으로 정렬

	cout << solution() << endl;

	return 0;
}

해설

  • solution() : K 횟수 만큼 각 계절마다 작업을 진행하고, 총 나무의 수를 반환
  • check_boundary() : 나무를 번식시킬때 필요한 인덱스 체크
  • add_new_tree() : 나무를 각 여덟 방향으로 번식 시킴
  • sorting_trees() : 같은 땅에 존재하는 나무들을 나이 순으로 정렬
  • spring() : 모든 나무들이 영양분을 섭취하고 나이 1 증가시킴
  • summer() : 양분 섭취를 못한 나무들이 (나이/2)만큼 양분으로 변환 됨
  • fall() : 땅에 위치한 나무의 나이가 5의 배수라면, 인접한 8개의 칸에 나이가 1인 나무 번식
  • winter() : 로봇이 땅에 양분 추가

앗 이걸 생각 못했네?

  • 이런 문제에서 쉽게 실수 할 수 있는 부분은 같은 땅에 존재 하는 나무들의 나이 순서에 따른 정렬 문제라고 생각합니다.
    • 같은 (r,c) 위치에서 나무들의 나이값들을 1차원 배열로 저장하면서, 새로운 나무들을 추가할 때 마다 배열에 앞에 추가하는 것과 뒤로 추가하는 것에 따라 처리 방법이 달라질 수 있습니다.
      (이 문제 풀이에서는 습관적으로 sort함수가 사용되었지만, 어린 나무를 매번 맨 앞에 추가함으로써 사실상 sort가 필요 없을 수 있습니다…)
  • 초기에 주어지는 나무 위치 값이 1 ~ N 임을 주의히세요.
  • N x N 만큼의 2차원 배열을 모두 순회하는 것이 아닌 나무가 존재하는 땅의 인덱스만 저장하는 배열을 따로 만들어 시간을 감소시킬 수도 있습니다. (N의 크기가 충분히 커진다면,)

다른 풀이

16235번 나무재테크 1차 풀이

기타 다른 문제 풀이 코드 (github)