[백준] 19235 나무 재테크

문제보기

간단한 구현문제로, 요구사항만 꼼꼼하게 옮겨주면 된다.

처음에는 봄/여름/가을/겨울을 나눠서 진행했다가 시간초과가 발생해서 ㅠ

문제를 다시 읽어보니 봄&여름 , 가을&겨울은 함께 수행해도 괜찮을것 같아 수정 후 제출했더니 통과되었다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;
// 나무 클래스 
class Tree{
  int age;
  Tree(int age){
    this.age = age;
  }
}

public class Main {
	// 8 방향
  static int[] dx = {1, 1, 1, -1, -1, -1, 0, 0};
  static int[] dy = {1, 0, -1, -1, 0, 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[][] map = new int[n][n]; // 처음에 주어지는 맵
    int[][] a = new int[n][n]; // 겨울에 추가될 양분 맵
    ArrayList<Tree>[][] trees = (ArrayList<Tree>[][]) new ArrayList[n][n]; // 2차 배열의 요소로 리스트를 사용했다 

    // 초기화
    for(int i = 0 ; i < n ; i++) {
      st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < n ; j++) {
        map[i][j] = 5; 
        a[i][j] = Integer.parseInt(st.nextToken());
        trees[i][j] = new ArrayList<Tree>();
      }
    }
		
    // 나무 입력받기 
    for(int i = 0 ; i < m ; i++) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken())-1;
      int y = Integer.parseInt(st.nextToken())-1;
      int age = Integer.parseInt(st.nextToken());
      trees[x][y].add(new Tree(age));
    }


    while( k-- > 0 ) { // k년 동안 반복한다

      // spring & summer
      for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
          if(trees[i][j].size() == 0) continue; // 나무가 없다면 컨티뉴
					
          // 둘 이상의 나무가 있다면 나이순으로 정렬해줌
          if(trees[i][j].size() > 1) {
            trees[i][j].sort(new Comparator<Tree>() {
              @Override
              public int compare(Tree o1, Tree o2) {
                if(o1.age < o2.age) {
                  return -1;
                }else {
                  return 1;
                }
              }
            });
          }
     
          int hp = 0; // 죽은 나무로부터 얻을 양분의 합
          for(int t = 0 ; t < trees[i][j].size(); t++) {					
            Tree tree = trees[i][j].get(t);
            if(map[i][j] >= tree.age) { // 땅이 양분을 줄 수 있다면
              map[i][j] -= tree.age++; // 준다
            }else { // 양분을 줄 수 없다면 
              hp += tree.age/2; // 양분이 되어라!
              trees[i][j].remove(t--); // 리스트에서 삭제
            }
          }
          map[i][j] += hp; // 시체들로부터 만든 양분을 추가한다 
        }
      }

      // fall & winter
      for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {

          int size = trees[i][j].size();

          if(size > 0) { // 하나 이상의 나무가 있다면
            for(Tree tree : trees[i][j]) {
              if(tree.age%5 == 0) { // 나이가 5의 배수라면
                for(int d = 0 ; d < 8 ; d++) { // 8 방향에 대하여
                  int nx = i + dx[d];
                  int ny = j + dy[d];
		
		// 맵에 존재한다면
                  if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
			// 나이가 1인 나무를 새로 심는다
                    trees[nx][ny].add(new Tree(1));
                  }
                }
              }
            }
          }
          map[i][j] += a[i][j]; // 겨울에는 양분을 추가해준다
        }
      }
    }
    // 나무의 수를 세어준다 (죽은건 삭제되므로 살아있냐 여부는 신경안써도됨)
    int cnt = 0;
    for(int i = 0 ; i < n ; i++) {
      for(int j = 0 ; j < n ; j++) {
        cnt += trees[i][j].size();
      }
    }
	// 출력
    System.out.println(cnt);
  }
}