[JS] 백준 16235 : 나무 재테크

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

16235번: 나무 재테크

 

 

📋풀이방법

1. 먼저 주어진 양분추가를 위한 winter배열과 현재 양분인 arr배열을 5로 초기화해서 선언한다.

2. 처음 나무를 심는 좌표를 [ y좌표, x좌표, 나이, 죽은나무인지 판별] 로 tree배열에 push한다.

3. 나무를 나이순으로 내림차순한다.

4. 주어진 k년수로 아래 명령을 반복한다.

5. 봄

 -tree배열을 나이가어린 나무를 위해 뒤에서부터 순회한다 -> 가을에 나무가 번식할때 어린 나무들은 뒤에서부터 push로 넣어줬기 때문에

 -양분이 충분하면 나무의 나이만큼 빼주고, 나무는 한살 증가 

 -양분이 충분하지 못하면 나무에 [ 죽은 나무인지 판별] 을 체크

6. 여름

 -tree배열을 filter하면서 [죽은나무인지 판별]에따라 아래명령수행

 -죽은나무가 아니면 tree 다시 넣어주기 -true

 -죽은나무면 양분이되어야함

 ->arr배열에 해당 죽은나무 좌표로 나이/2 값을 누적해줌 -> false로 filter함

7.가을

 -tree배열을 순회해줌

 -8방향으로 좌표가 넘어가지 않으면 tree에 1살의 나이로 push해줌

8.겨울

 -arr배열의 값을 처음선언했던 winter의 값들로 각각 좌표마다 더해줌

9.반복이 끝나면 tree에 남아있는 나무들의 수를 구하면 정답

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,M,K]=input.shift().split(" ").map(Number);
let arr=Array.from({length:N},()=>Array(N).fill(5));
let winter=[];
for(var i=0;i<N;i++){
    winter.push(input.shift().split(" ").map(Number));
}
let tree=[];

for(var i=0;i<M;i++){
	let [y,x,year]=input.shift().split(" ").map(Number);
	tree.push([y-1,x-1,year,0]);
}

let dx=[-1,0,1,-1,1,-1,0,1];
let dy=[-1,-1,-1,0,0,1,1,1];

tree.sort((a,b)=>b[2]-a[2]);

for(var t=0;t<K;t++){
	//봄
	//push로 가을에 뒤에 어린나이부터 넣어줬기 때문에 뒤에서부터 순회
	for(var i=tree.length-1; i>=0 ;i--){
		let [y,x,age,check]=tree[i];

		if(arr[y][x]>=age){
			arr[y][x]-=age;
			tree[i][2]++;
		}
		else{
			tree[i][3]=-1;
		}
	}

	tree=tree.filter((v)=>{
		if(v[3]==0) return true;
		else{
			let [y,x,age,check]=v;

			arr[y][x]+=Math.floor(age/2);
			return false;
		}
	})
	
	//가을
	//push로 뒤에 넣어줘야 forEach로 순회중에 꼬이지않는다.
	tree.forEach((v)=>{
		let [y,x,age,check]=v;
		if(age%5==0){
			for(var z=0;z<8;z++){
				let nx=x+dx[z];
				let ny=y+dy[z];

				if(nx>=0 && ny>=0 && nx<N && ny<N){
					tree.push([ny,nx,1,0]);	
				}
			}
		}		
	});
	//겨울
	for(var i=0;i<N;i++){
		for(var j=0;j<N;j++){
			arr[i][j]+=winter[i][j];
		}
	}
	
}

console.log(tree.length)

 

💢어려웠던 점

1. 시간초과가걸림

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,M,K]=input.shift().split(" ").map(Number);
let arr=Array.from({length:N},()=>Array(N).fill(5));
let winter=[];
for(var i=0;i<N;i++){
    winter.push(input.shift().split(" ").map(Number));
}

let temp=Array.from({length:N},()=>Array(N).fill([]));
for(var i=0;i<M;i++){
	let [y,x,year]=input.shift().split(" ").map(Number);
	temp[y-1][x-1]=[...temp[y-1][x-1],year]
}

let dx=[-1,0,1,-1,1,-1,0,1];
let dy=[-1,-1,-1,0,0,1,1,1];
let result=0;
let dead_tree=Array.from({length:N},()=>Array(N).fill(0));
for(var t=0;t<K;t++){
	result=0;
	//봄
	for(var i=0;i<N;i++){
		for(var j=0;j<N;j++){
			if(temp[i][j].length!=0){
				for(var z=0;z<temp[i][j].length;z++){
					if(arr[i][j]>=temp[i][j][z]){
						arr[i][j]-=temp[i][j][z];
						temp[i][j][z]+=1;
					}
					//죽은나무
					else{
						dead_tree[i][j]+=Math.floor(temp[i][j][z]/2);
						temp[i][j].splice(z,1);
						z--;
					}
					

				}
			}
			arr[i][j]+=dead_tree[i][j];
			dead_tree[i][j]=0;
		}
	}
	

	//가을
	for(var i=0;i<N;i++){
		for(var j=0;j<N;j++){
			if(temp[i][j].length!=0){
				for(var v=0;v<temp[i][j].length;v++){
					if( temp[i][j][v] % 5==0){
						for(var z=0;z<8;z++){
							let nx=j+dx[z];
							let ny=i+dy[z];
							if(nx>=0 && ny>=0 && nx<N && ny<N){
								temp[ny][nx]=[1,...temp[ny][nx]];
								
							}
						}
					}		
				}
			}
		}
	}
	//겨울
	for(var i=0;i<N;i++){
		for(var j=0;j<N;j++){
			result+=temp[i][j].length
			arr[i][j]+=winter[i][j];
		}
	}
	
}
console.log(result)

-모든 명령을 2중for문으로 일일이 계산해서 시간초과가 걸림

-모든 상황에 2차원배열을 만들어서 진행함

 -죽은나무가 양분이 되는 값을 저장한 배열 dead_tree

 -현재 나무가 심어져있는 temp배열

 -현재 양분을 표시하는 arr배열

 -로봇으로 양분을 추가하는 winter배열

-이로 인해 시간초과 발생

-또한 이 코드에서 봄에 양분을 먹지못했을때의 해결하는 방법을 파악하기까지 시간이 오래걸림