알고리즘/시뮬레이션

BOJ 백준 16235 나무 재테크 [JAVA]

kyjdummy 2025. 9. 4. 22:00

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

 

[ 문제 요약 ]

  • N * N 크기의 땅이 있다. 칸은 1 * 1 크기로 나누어져 있다.
  • 각 칸은 (y, x)로 y는 세로 x는 가로를 의미한다. y, x는 1부터 시작한다.
  • 로봇은 모든 1 * 1칸에 들어있는 양분을 조사해 전송한다.
  • 가장 처음 양분은 모든 칸에 5만큼 들어있다. 나무 재테크를 할 건데, 이는 작은 묘목을 구매해 어느 정도 키운 후 팔아서 수익을 얻는 재테크이다.
  • 나무를 M 개 심었다. 1 * 1크기 칸에 여러 개의 나무가 심어져 있을 수 있다.
  • 이 나무는 봄, 여름, 가을, 겨울을 순서대로 보내며 아래 과정을 반복한다.
  • 봄 : 나무가 자신의 나이만큼 양분을 먹고 나이가 1증가한다. 각 나무는 나무가 있는 1*1 크기의 칸에 있는 양분만 먹을 수 있고 한 칸에 여러 나무가 있다면 나이가 어린 나무부터 양분을 먹는다. 만약 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
  • 여름 : 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
  • 가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
  • 겨울 : 땅을 돌아다니며 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[y][x]이고 입력으로 주어진다.
  • K 년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하라.

 

[ 테스트 케이스 설명 ]

5 2 1// 맵크기(1<=10), 나무개수(1<=N^2), 목표년수(1<=1000)
2 3 2 3 2 // N개 줄에 배열 A의 값이 주어진다.
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3 // 나무 개수 만큼 나무정보가 주어지며 y, x, 나무의 나이가 주어진다.(1<=100)
3 2 3
목표년수가 지난 후 살아남은 나무의 수를 출력 : 2

 

 

[ 알고리즘 분류 ]

  • 구현
  • 자료 구조
  • 시뮬레이션

 

[ 문제 해설 ]

 

문제 요구사항에 맞게 구현해 주면 되는 간단한 문제입니다.

 

나이가 작은 나무부터 양분을 먹는다고 해서 전체를 순회하며 정렬을 계속해 준다면 시간 초과일 수 있습니다.

 

ArrayDeque 자료구조를 쓰면 최초 나무 나이에 대해 한 번만 정렬하면 후에 나무가 번식하고, 양분을 먹을 때 쉽게 구현할 수 있습니다. (나무가 번식할 때 ArrayDeque의 맨 앞에 데이터를 추가하면 됩니다.)

 

봄 가을만 잘 구현하면 됩니다.

 

봄은 어쨌든 모든 나무가 양분을 먹거나, 죽거나 둘 중 하나입니다.

 

가을은 맵을 순회하며 나이가 5의 배수인 경우 주변에 나무를 추가하는데, 탐색과 동시에 주변 큐에 데이터를 추가해버리면 현재 추가한 데이터가 후에 영향을 미치기 때문에 탐색을 모두 마치고 추가될 나무는 나중에 한 번 더 탐색하며 추가합니다.

 

봄, 여름, 가을, 겨울을 따로 구현한 코드와 봄 + 여름, 가을 + 겨울을 구현한 코드 두 개를 작성해 봤습니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Main{
	
	static final int dxy[][] = {{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
	static int N, T, K;
	static int[][] plus, food, addTree;
	static ArrayList<Integer>[][] init;
	static ArrayDeque<Integer>[][] map;
	static ArrayDeque<Integer>[][] death;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 맵크기(1<=10)
		T = Integer.parseInt(st.nextToken());// 나무개수(1<=N^2)
		K = Integer.parseInt(st.nextToken());// 목표년수(1<=1000)
		plus = new int[N][N];// 매년 추가될 양분
		food = new int[N][N];// 현재 양분
		addTree = new int[N][N];// 가을에 번식하는 나무를 담음
		map = new ArrayDeque[N][N];// 현재나무의 나이를 담음
		init = new ArrayList[N][N];// 최초 나무를 담음
		death = new ArrayDeque[N][N];// 죽은 나무의 나이를 담음
		
		for(int y=0; y<N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<N; x++)
			{
				plus[y][x] = Integer.parseInt(st.nextToken());
				food[y][x] = 5;
				map[y][x] = new ArrayDeque<>();
				init[y][x] = new ArrayList<>();
				death[y][x] = new ArrayDeque<>();
			}
		}
		
		for(int i=0; i<T; i++)
		{
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int z = Integer.parseInt(st.nextToken());// 나무 나이
			init[y][x].add(z);// 최초 나무 나이를 담음
		}
		
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(init[y][x].size() > 1)// 나무나이 정렬
					Collections.sort(init[y][x]);
				
				for(int age : init[y][x])
					map[y][x].addLast(age);// 나무 나이를 오름차순으로 map에 담음
			}
		}
		
		while(K-->0)
		{
			spring();
			summer();
			fall();
			winter();
		}
		
		System.out.print( count() );
	}
	static void winter()
	{
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
				food[y][x] += plus[y][x];
	}
	static void fall()
	{
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				int size = map[y][x].size();
				while(size-->0)
				{
					int age = map[y][x].pollFirst();
					
					if(age % 5 == 0)
						treeSet(y, x);
					
					map[y][x].addLast(age);
				}
			}
		}
		
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
			{
				while(addTree[y][x]-- > 0)// 추가된 나무만큼 그곳에 추가한다.
					map[y][x].addFirst(1);
				
				addTree[y][x] = 0;
			}

	}
	static void treeSet(int y, int x) {
		for(int xy[] : dxy)
		{
			int ny = y + xy[0];
			int nx = x + xy[1];
			if(0<=ny && 0<=nx && ny<N && nx<N)
				addTree[ny][nx]++;
		}
	}
	static void summer() {
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
				while(!death[y][x].isEmpty())
					food[y][x] += death[y][x].pollFirst() / 2;
	}
	static void spring() {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				int size = map[y][x].size();
				
				while(size-->0)
				{
					int age = map[y][x].pollFirst();
					if(food[y][x] < age)// 나이만큼 양분을 먹지 못하면 죽음
					{
						death[y][x].add(age);
						continue;
					}
					
					food[y][x] -= age;
					map[y][x].addLast(age + 1);
				}
			}
		}
	}
	static int count() {
		int cnt = 0;
		
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
				cnt += map[y][x].size();
		
		return cnt;
	}
}

 

 

[ 정답 코드 2 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Main{
	
	static final int dxy[][] = {{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
	static int N, T, K;
	static int[][] plus, food, addTree;
	static ArrayList<Integer>[][] init;
	static ArrayDeque<Integer>[][] map;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 맵크기(1<=10)
		T = Integer.parseInt(st.nextToken());// 나무개수(1<=N^2)
		K = Integer.parseInt(st.nextToken());// 목표년수(1<=1000)
		plus = new int[N][N];// 매년 추가될 양분
		food = new int[N][N];// 현재 양분
		addTree = new int[N][N];// 가을에 번식하는 나무를 담음
		map = new ArrayDeque[N][N];// 현재나무의 나이를 담음
		init = new ArrayList[N][N];// 최초 나무를 담음
		
		for(int y=0; y<N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<N; x++)
			{
				plus[y][x] = Integer.parseInt(st.nextToken());
				food[y][x] = 5;
				map[y][x] = new ArrayDeque<>();
				init[y][x] = new ArrayList<>();
			}
		}
		
		for(int i=0; i<T; i++)
		{
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int z = Integer.parseInt(st.nextToken());// 나무 나이
			init[y][x].add(z);// 최초 나무 나이를 담음
		}
		
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(init[y][x].size() > 1)// 나무나이 정렬
					Collections.sort(init[y][x]);
				
				for(int age : init[y][x])
					map[y][x].addLast(age);// 나무 나이를 오름차순으로 map에 담음
			}
		}
		
		while(K-->0)
		{
			springAndSummer();
			fallAndWinter();
		}
		
		System.out.print( count() );
	}
	static void fallAndWinter()
	{
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				int size = map[y][x].size();
				while(size-->0)
				{
					int age = map[y][x].pollFirst();
					
					if(age % 5 == 0)
						treeSet(y, x);
					
					map[y][x].addLast(age);
				}
			}
		}
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
			{
				while(addTree[y][x]-- > 0)// 추가된 나무만큼 그곳에 추가한다.
					map[y][x].addFirst(1);
				
				addTree[y][x] = 0;
				// winter 로직
				food[y][x] += plus[y][x];
			}

	}
	static void treeSet(int y, int x) {
		for(int xy[] : dxy)
		{
			int ny = y + xy[0];
			int nx = x + xy[1];
			if(0<=ny && 0<=nx && ny<N && nx<N)
				addTree[ny][nx]++;
		}
	}
	static void springAndSummer() {
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				boolean isSummer = false;
				int size = map[y][x].size();
				
				while(size-->0)
				{
					int age = map[y][x].pollFirst();
					if(isSummer || food[y][x] < age)// 나이만큼 양분을 먹지 못하면 죽음
					{
						food[y][x] += age / 2; // 나이의 절반을 양분으로 만듦
						isSummer = true;// 한번 summer 로직을 타면 계속 탄다. 오름차순이기 때문
						continue;
					}
					
					food[y][x] -= age;
					map[y][x].addLast(age + 1);
				}
			}
		}
	}
	static int count() {
		int cnt = 0;
		
		for(int y=0; y<N; y++)
			for(int x=0; x<N; x++)
				cnt += map[y][x].size();
		
		return cnt;
	}
}

 

 

'알고리즘 > 시뮬레이션' 카테고리의 다른 글

BOJ 백준 20056 마법사 상어와 파이어볼 [JAVA]  (0) 2025.09.10
BOJ 백준 21610 마법사 상어와 비바라기 [JAVA]  (0) 2025.09.09
BOJ 백준 17140 이차원 배열과 연산 [JAVA]  (0) 2025.09.03
BOJ 백준 15685 드래곤 커브 [JAVA]  (0) 2025.09.02
BOJ 백준 20055 컨베이어 벨트 위의 로봇 [JAVA]  (0) 2025.09.01

'알고리즘/시뮬레이션'의 다른글

  • 현재글BOJ 백준 16235 나무 재테크 [JAVA]

관련글

티스토리툴바