BOJ G3 16235 나무재테크 JAVA

 

 

16235번: 나무 재테크

---

 

문제 읽기

실수 없이 구현하면 되는 시뮬레이션 문제이다. 문제를 읽으면서 실수할 수 있는 부분을 체크하면서 읽었다.

• r, c는 1부터 시작
• 초기 양분은 5부터

그 다음 자료구조를 정했다.

• 나무 : 나이만 필요하므로 그냥 int형
• Cell : 양분의 양(int), 살아있는 나무(list), 죽은 나무(list)

나무는 그냥 int형으로 정했고 각각의 cell은 class로 정의했다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_16235_나무재테크 {
	static class Cell{
		int good;
		List<Integer> liveTree;
		List<Integer> deadTree;
		public Cell(int good, List<Integer> liveTree, List<Integer> deadTree) {
			super();
			this.good = good;
			this.liveTree = liveTree;
			this.deadTree = deadTree;
		}
	}
	
	static int N, M, K; //NxN, 나무 수, K년
	static Cell[][] map;
	static int[][] A;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		//A입력
		A = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//맵 초기화
		map = new Cell[N][N];
		//r, c 다 해줘야 함. 아니면 null pointer error
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				//초기에는 5 만큼의 양분 존재
				map[r][c] = new Cell(5, new ArrayList<>(), new ArrayList<>());
			}
		}
		
		//나무 입력
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			int age = Integer.parseInt(st.nextToken());
			map[r][c].liveTree.add(age);
		}
		
		//logic
		while(K-- > 0) {

			//봄 : 양분 섭취
			spring();
			
			//여름 : 죽은 나무가 양분으로
			summer();
			
			//가을 : 나무 번식. age = 5의 배수
			fall();
			
			//겨울 : 기기가 양분 추가
			winter();
		}
		
		//K년 후.. 살아있는 나무의 개수
		int cnt = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				cnt += map[r][c].liveTree.size();
			}
		}
		System.out.println(cnt);
	}

	private static void spring() {
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				//매 cell마다 나무들을 스캔하여 나이 먹임
				//오름차순 정렬 후 스캔
				Collections.sort(map[r][c].liveTree); //디폴트가 오름차순
				
				int deadIdx = -1;
				for (int i = 0; i < map[r][c].liveTree.size(); i++) {
					//나이만큼의 양분이 있는지 체크
					int age = map[r][c].liveTree.get(i);
					if (map[r][c].good >= age) {
						map[r][c].good -= age;
						map[r][c].liveTree.set(i, age+1); //나이 증가!!
					}
					else {
						//죽음. 오름차순 정렬이기 때문에 뒤에 있는 것도 다 죽음. 반복문 밖에서 처리
						deadIdx = i; //i~끝까지 다 죽음
						break; //빼먹음!!
					}
				}
				
				//죽은 나무는 live에서 뺴고, dead에 넣음. remove를 쓰기 위해 끝에서부터 지움
				if (deadIdx != -1) {
					for (int i = map[r][c].liveTree.size() - 1; i >= deadIdx; i--) {
						int deadTree = map[r][c].liveTree.get(i);
						map[r][c].liveTree.remove(i);
						map[r][c].deadTree.add(deadTree);
					}
				}
				
			}
		}
	}

	private static void summer() {
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				for (int age : map[r][c].deadTree) {
					//나이 / 2 = 새로운 양분
					map[r][c].good += (age / 2); //소수점 아래는 자동 버림
				}
				map[r][c].deadTree.clear(); //다 양분으로 변함
			}
		}
	}

	static int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
	private static void fall() {
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				for (int age : map[r][c].liveTree) {
					if (age % 5 == 0) {
						//인접 8방에 나이 1인 나무 생성
						spread(r, c);
					}
				}
			}
		}
	}

	private static void spread(int r, int c) {
		for (int di = 0; di < 8; di++) {
			int nr = r + dr[di];
			int nc = c + dc[di];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			//아기나무
			map[nr][nc].liveTree.add(1);
		}
	}

	private static void winter() {
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				map[r][c].good += A[r][c];
			}
		}
	}
}

---

실수한 부분

원소 삭제 : 하려고 한 게 있으면 까먹지 않게 주석으로 메모하자

죽은 나무를 살아있는 나무 리스트에서 지울 때 deadIdx를 정해서 지웠는데, break가 빠져서 마지막 답이 나오지 않았다. 이 부분 주의 !

이차원 배열 할당 : NULL Pointer Error

사용자 정의 class로 이차원 배열 선언 시 이중 for문을 통해 일일이 초기화 필수!!