백준 16235 나무 재테크 - 삼성 SW 역량 테스트 기출

백준 16235 나무 재테크 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

16235번: 나무 재테크

 

2. 문제 해결에 대한 아이디어

1. 각 칸에는 여러 개의 나무가 있을 수 있고, 양분 정보도 포함하고 있어야 한다.

2. 따라서 나무 클래스(Tree)를 만들고, 나무 리스트와 양분 정보를 포함하는 땅 클래스(Tile)를 만들었다.

3. 봄에서 나이가 어린순으로 양분을 먹는다 했으므로, 나무 리스트를 나무의 나이를 기준으로 오름차순 해야 한다.

4. 봄에서 죽은 나무를 관리할, 죽은 나무 리스트가 필요하다. --> deadTree

5. 여름, 가을은 단순 구현이다.

6. 초기 입력으로 주어지는 영양분 정보는 따로 저장해 두고 겨울에 이를 사용한다.

7. K 년이 지났을 때, 땅을 순회하며 나무 리스트의 사이즈를 모두 더하여 답을 출력한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	static int N, M, K;

	static Tile[][] board;
	static List<Tree> deadTree;
	static int[] dirY = { 0, 0, 1, 1, 1, -1, -1, -1 }; // 8 방향
	static int[] dirX = { 1, -1, 0, 1, -1, 0, 1, -1 }; // 8 방향
	static int[][] robotFood;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nmk = br.readLine().split(" ");
		N = Integer.parseInt(nmk[0]);
		M = Integer.parseInt(nmk[1]);
		K = Integer.parseInt(nmk[2]);

		board = new Tile[N][N];
		robotFood = new int[N][N];
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				int food = Integer.parseInt(line[j]);
				robotFood[i][j] = food; // 겨울에 로봇이 주입할 영양분
				board[i][j] = new Tile(5); // 땅의 기본 영양분은 5
			}
		}

		for (int i = 0; i < M; i++) {
			String[] line = br.readLine().split(" ");
			int y = Integer.parseInt(line[0]) - 1;
			int x = Integer.parseInt(line[1]) - 1;
			int z = Integer.parseInt(line[2]);
			board[y][x].trees.add(new Tree(y, x, z));
		}

		while (K-- > 0) {
			// 죽은 나무 리스트 초기화
			deadTree = new ArrayList<>(); 

			// 봄
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!board[i][j].trees.isEmpty()) {
						 // 나이 오름차순으로 나무 정렬
						Collections.sort(board[i][j].trees);
						List<Tree> treeList = board[i][j].trees;

						int k = 0;
						for (; k < treeList.size(); k++) {
							if (board[i][j].food >= treeList.get(k).z) {
								board[i][j].food -= treeList.get(k).z;
								treeList.get(k).z++;
							} else {
								for (; k < treeList.size(); k++) {
									 // for문에서 다시 ++ 가 되므로 현재 지워진 인덱스값을 다음 차례에 보기위해
									deadTree.add(treeList.remove(k--));
																		
								}
								break;
							}
						}

					}
				}
			}

			// 여름
			for (int i = 0; i < deadTree.size(); i++) {
				Tree dead = deadTree.get(i);
				board[dead.y][dead.x].food += dead.z / 2;
			}

			// 가을
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					List<Tree> trees = board[i][j].trees;
					for (int k = 0; k < trees.size(); k++) {
						Tree t = trees.get(k);
						if (t.z % 5 == 0) {
							int y = t.y;
							int x = t.x;
							for (int d = 0; d < 8; d++) {
								int yy = t.y + dirY[d];
								int xx = t.x + dirX[d];
								if (yy < 0 || xx < 0 || yy >= N || xx >= N)
									continue;
								board[yy][xx].trees.add(new Tree(yy, xx, 1));
							}
						}
					}
				}
			}

			// 겨울
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					board[i][j].food += robotFood[i][j];
				}
			}
		}
		int live = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				live += board[i][j].trees.size();
			}
		}

		System.out.println(live);
	}

}

class Tree implements Comparable<Tree> {
	int y, x, z;

	public Tree(int y, int x, int z) {
		super();
		this.y = y;
		this.x = x;
		this.z = z;
	}

	@Override
	public int compareTo(Tree o) {
		return this.z - o.z;
	}

}

class Tile {
	List<Tree> trees = new ArrayList<>();
	int food;

	public Tile(int food) {
		super();

		this.food = food;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 자바에서 Comparable을 써본 적이 없어서, 객체의 값을 기준으로 소팅하는 방법을 몰라 헤맸다.

2. 객체의 값을 기준으로 소팅하는 로직은 자주 나오는 유형이므로, 익숙해지도록 해야겠다.

3. 어쩌다 보니 for문의 depth가 깊어져, 제대로 구현하고 있는지 의문이 들었지만 일단 통과는 했다.