[백준] 16235 나무 재테크 (Java)

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

16235번: 나무 재테크

 

구현 + 시뮬레이션 문제로 보인다

 

1 <= N <= 10, 최대 땅의 개수는 100개이다

1 <= M <= N^2, 마찬가지로 '처음' 심을 수 있는 나무의 개수는 100개이다 (번식 제외)

1 <= A[r][c] <= 100 으로 한 해에 추가되는 그 땅의 양분은 100이 최대이다

---

 

어림잡아 계산해도 출력할 나무의 개수가 int형을 넘지는 않아 보인다

한 해에 일어나는 일의 순서를 정리하자면,

양분흡수, 나이증가 -> 죽은 나무 양분으로 변환 -> 나무 번식 -> 땅에 양분 추가

 

하나씩 순차적으로 구현해 나가면 큰 어려움 없어 보이는 문제다

하지만 약 2개월 만에 푸는 문제라 그런지 절었던 부분이 많았다...

그 부분을 천천히 되짚어보자

 

---

 

어떤 자료구조를 사용할 것인가

 

양분을 담고있는 N*N 개의 땅은 고민할 것도 없이 배열을 사용

로봇이 겨울마다 양분을 주입하는 것 또한 N*N 크기이기 때문에, 배열을 생성하여 값을 주었다

고민이 시작된 것은 세가지 정보(x, y, age)를 가진 나무의 정보이다

머리가 굳어서 클래스를 만든다는 선택지를 떠올리기까지 너무 오래 걸렸다

결과적으로 ArrayList<Tree> 로 진행했다

또한 클래스는 compareTo 를 사용하여 age가 적은순으로 정렬하도록 만들었다

 

---

 

서로 복잡하게 상호작용하는 로직이 아니기 때문에 각각 봄, 여름, 가을, 겨울에 맞게 로직을 짜면 된다

물론 말 처럼 쉽게 풀리지는 않았다

 

봄 -

양분을 흡수할 수 있다면 나이를 증가시키고, 흡수가 불가능하다면 리스트에서 버려야 한다

그럼 결국 처음부터 remove로 꺼내고, 흡수할 수 있다면 age++ 이후에 다시 add 하면 된다는 결론이 나온다

그리고 이후 여름엔 죽은 나무들의 age / 2 만큼 땅의 양분을 주어야 하니,

죽은 나무는 새로운 자료구조에 정보를 다시 담았다

하지만 위 방법은 오답이다

 

이쯤해서 혼자 풀이하는건 포기하고 참고 자료를 찾아다니며 풀이했다

위 방법에서 오답을 받은 이유는, remove를 사용할 경우 기껏 정렬한 list의 순서가 무너진다고 한다

결국 데이터를 꺼냈다가 다시 집어 넣더라도, 순서를 보장할 방법을 찾아야 했다

해답은 Queue의 사용이다

for(int i = 0; i < trees.size();) {
        		Tree cur = trees.poll();
        		
        		if(lands[cur.x][cur.y] >= cur.age) {
        			lands[cur.x][cur.y] -= cur.age;
        			cur.age++;
        			i++;
        			trees.add(cur);
        		} else {
        			deadTrees.add(cur);
        		}
        	}

q.poll 로 데이터를 뽑는 대신, i 의 범위에 제한을 두어 모든 나무가 양분을 흡수하더라도

한 나무가 두번 이상 로직을 실행하는 경우는 제한했다

 

 

죽은 나무의 정보를 담는 자료구조는 List가 됐든, Queue가 됐든 상관 없이 정답을 받을 수 있다

보통 이런 경우에 많은 사람들이 Queue를 사용하는 것이 기억에 남는다

그런데 속도는 List가 더 빠르고, 개인적으로 익숙하기도 해서 List를 선택했다

 

여름-

놀랍게도 5의 배수를 어떻게 가려낼지를 혼자 생각해내지 못했다

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

제발 배수를 보면 % 를 활용할 생각을 하자

 

가을-

상하좌우, 대각선을 dx[], dy[] 배열로 전역 필드에서 생성했다

나머지는 흔한 bfs 이다

 

겨울-

i, j 로 탐색하며 robot의 값을 lands에 더해주면 끝이다

 

 

전체코드

package org.opentutorials.javatutorials.free;

import java.io.*;
import java.util.*;

class freetutorials{
	
	static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
	static int[] dy = {0, 0, -1, 1, -1, 1, 1, -1};
	
	public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        int[][] lands = new int[N+1][N+1];
        int[][] robot = new int[N+1][N+1];
        Deque<Tree> trees = new LinkedList<>();
        
        for(int i = 1; i <= N; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	for(int j = 1; j <= N; j++) {
        		robot[i][j] = Integer.parseInt(st.nextToken());
        		lands[i][j] = 5;
        	}
        }
        
        for(int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	int x = Integer.parseInt(st.nextToken());
        	int y = Integer.parseInt(st.nextToken());
        	int age = Integer.parseInt(st.nextToken());
        	
        	trees.add(new Tree(x, y, age));
        }
        
        while(K --> 0) {
        	List<Tree> deadTrees = new ArrayList<>();
        	
        	// 봄
        	for(int i = 0; i < trees.size();) {
        		Tree cur = trees.poll();
        		
        		if(lands[cur.x][cur.y] >= cur.age) {
        			lands[cur.x][cur.y] -= cur.age;
        			cur.age++;
        			i++;
        			trees.add(cur);
        		} else {
        			deadTrees.add(cur);
        		}
        	}
        	
        	// 여름
        	for(Tree t : deadTrees) {
        		lands[t.x][t.y] += t.age / 2; 
        	}
        	
        	// 가을
        	Queue<Tree> newTree = new LinkedList<>();
        	for(Tree t : trees) {
        		if(t.age % 5 == 0) {
        			newTree.add(t);
        		}
        	}
        	
        	while(!newTree.isEmpty()) {
        		Tree t = newTree.poll();
        		
        		for(int i = 0; i < 8; i++) {
        			int nx = dx[i] + t.x;
        			int ny = dy[i] + t.y;
        			
        			if(nx >= 1 && ny >= 1 && nx <= N && ny <= N) {
        				trees.addFirst(new Tree(nx, ny, 1));
        			}
        		}
        	}
        	
        	// 겨울
        	for(int i = 1; i <= N; i++) {
        		for(int j = 1; j <= N; j++) {
        			lands[i][j] += robot[i][j];
        		}
        	}
        }
        
        System.out.println(trees.size());
	}
}
class Tree implements Comparable<Tree>{
	int x, y, age;
	
	public Tree(int x, int y, int age) {
		super();
		this.x = x;
		this.y = y;
		this.age = age;
	}
	
	@Override
	public int compareTo(Tree o) {
		return this.age - o.age;
	}
}

 

 

 

 

정리

순수히 알고리즘만 공부하던 때와 다르게,

개발 공부를 하다오니 조금더 자료구조의 사용과 데이터의 취급법에 대해 깊은 고민을 할 수 있게 된 것 같다

당장 알고리즘 실력은 다운그레이드가 확실하지만, 길게 보면 확실히 긍정적인 영향을 끼친 것 같다

앞으로는 알고리즘과 개발 공부를 병행하며 양쪽다 상승곡선을 그릴 수 있도록 노력해보자