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

나무 재테크

📚 문제 설명

N * N 의 땅이 있고, 땅에 나무가 심어져 있다.
봄 - 여름 - 가을 - 겨울
이 지날 때 특정 과정을 반복하게 된다고 했을 때, K년이 지났을 때, 살아있는 나무의 수를 구하여라.
단, 모든 땅에는 처음에는 5의 양분이 있다.

각각의 계절에는 다음과 같은 과정을 거친다.

봄 - 나무가 자신의 나이만큼 양분을 먹고 나이가 증가한다. 만약 양분이 없다면, 나무는 죽고 양분은 어린 나무부터 먹는다.

여름 - 죽은 나무의 나이에서 2를 나눈 값만큼 땅에 양분이 추가 된다.

가을 - 나무의 나이가 5의 배수라면, 나무 주변 8개의 장소에 나이가 1인 나무가 생긴다.

겨울 - 겨울에는 로봇이 돌아다니며, A[행][열] 만큼의 양분이 땅에 추가 된다.

👨🏻‍💻 풀이 과정

이 문제에서 핵심은 나무를 어떻게 저장하는지에 달려있다.
매번 sort를 진행하기에는 너무 비효율적이고, 모든 땅에 있는 나무를 배열로 저장하기에는 배열의 크기가 너무 방대해 진다.
따라서 나무를 저장할 배열 trees를 만든 후에 나무의 나이를 내림차순으로 정렬을 진행하였다.
이렇게 만든 후에 새로운 나무는 어차피 나이가 1이기 때문에 자연스럽게 내림차순으로 항상 정렬이 된다.
그리고 배열의 요소로는 [행, 열, 나이, 살아있는지 여부] 를 저장하였다.

변수 생성 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const [N, M, K] = input.shift().split(' ').map(Number);
	// 겨울마다 추가할 양분
    const R2D2 = input.splice(0, N).map(v => v.split(' ').map(Number));
	// 나무 배열
    let trees = input.splice(0, M).map(v => (v).split(' ').map(Number));
	// 나무 배열 마지막에 살아있는지 여부를 확인할 변수 추가.
    trees = trees.map(v => {
        v.push(true)
        return v;
    });
	// 나무를 나이순으로 정렬
    trees.sort((a, b) => b[2] - a[2]);
	// 땅
    let MAP = new Array(N);
    for (let i = 0; i < N; i++) {
        MAP[i] = new Array(N).fill(5);
    }

여기까지 진행했으면, 사계절에 대한 함수는 매우 간단하다.

• 봄
  • trees 함수 마지막부터 확인하며, 양분을 먹여줌.
  • 만약 양분이 없다면, isLive 변수를 false로 변경.
• 여름
  • filter() 함수를 이용해 trees 변수에서 isLive 변수가 false 인 값을 찾아줌.
  • false인 나무를 찾아서 MAP 에 양분을 주고 filter() 를 통해 걸러줌.
• 가을
  • trees 배열을 돌며 age가 5의 배수라면, 8방향으로 나무 생성.
  • 단, MAP 을 벗어나면 안됨.
• 겨울
  • MAP 에 양분 추가.

사계절 함수

	// 봄
    const SPRING = () => {
      	// 내림차순이기 때문에 끝에서부터.
        for (let i = trees.length - 1; i >= 0; i--) {
            let [x, y, age, isLive] = trees[i];
          	// 양분이 있다면, 양분을 소비하고, 나이+1
            if (MAP[x - 1][y - 1] >= age) {
                MAP[x - 1][y - 1] -= age;
                age += 1;
            } else {
              	// 아니라면 나무 사망.
                isLive = false;
            }
            trees[i] = [x, y, age, isLive];
        }
    };
	// 여름
    const SUMMER = () => {
      	// 죽은 나무 필터링
        trees = trees.filter(v => {
            if (v[3]) {
                return true;
            } else {
              	// 죽은 나무의 나이 나누기 2만큼 양분 추가.
                MAP[v[0] - 1][v[1] - 1] += Math.floor(v[2] / 2);
                return false;
            }

        });
    };
	// 가을
    const AUTUMN = () => {
      	// 8방향
        let dx = [1, 1, 1, 0, 0, -1, -1, -1];
        let dy = [1, 0, -1, -1, 1, 1, 0, -1];
        for (let i = 0; i < trees.length; i++) {
            const [x, y, age, isLive] = trees[i];
          	// 나이가 5의 배수인 나무만.
            if (age % 5 === 0) {
                for (let j = 0; j < dx.length; j++) {
                    const nextX = x + dx[j] - 1;
                    const nextY = y + dy[j] - 1;
                  	// MAP 을 벗어나지 않게.
                    if (nextX < 0 || nextX >= N ||nextY < 0 || nextY >= N) continue;
                  	// 새 나무 추가.
                    trees.push([nextX + 1, nextY + 1, 1, true]);
                }
            }
        }
    };
	// 겨울
    const WINTER = () => {
        for (let i = 0; i < N; i++) {
          	// 양분 추가.
            for (let j = 0; j < N; j++) {
                MAP[i][j] += R2D2[i][j];
            }
        }
    };

그 후에는 K년 만큼 위의 사계절 함수를 실행하는데,
만약 trees 배열이 비어있으면 어차피 나무는 0개에서 증가할 수 없기 때문에 조건 하나를 추가 했다.

전체 코드

   let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const [N, M, K] = input.shift().split(' ').map(Number);
	// 겨울마다 추가할 양분
    const R2D2 = input.splice(0, N).map(v => v.split(' ').map(Number));
	// 나무 배열
    let trees = input.splice(0, M).map(v => (v).split(' ').map(Number));
	// 나무 배열 마지막에 살아있는지 여부를 확인할 변수 추가.
    trees = trees.map(v => {
        v.push(true)
        return v;
    });
	// 나무를 나이순으로 정렬
    trees.sort((a, b) => b[2] - a[2]);
	// 땅
    let MAP = new Array(N);
    for (let i = 0; i < N; i++) {
        MAP[i] = new Array(N).fill(5);
    }
    
        const SPRING = () => {
      	// 내림차순이기 때문에 끝에서부터.
        for (let i = trees.length - 1; i >= 0; i--) {
            let [x, y, age, isLive] = trees[i];
          	// 양분이 있다면, 양분을 소비하고, 나이+1
            if (MAP[x - 1][y - 1] >= age) {
                MAP[x - 1][y - 1] -= age;
                age += 1;
            } else {
              	// 아니라면 나무 사망.
                isLive = false;
            }
            trees[i] = [x, y, age, isLive];
        }
    };
	// 여름
    const SUMMER = () => {
      	// 죽은 나무 필터링
        trees = trees.filter(v => {
            if (v[3]) {
                return true;
            } else {
              	// 죽은 나무의 나이 나누기 2만큼 양분 추가.
                MAP[v[0] - 1][v[1] - 1] += Math.floor(v[2] / 2);
                return false;
            }

        });
    };
	// 가을
    const AUTUMN = () => {
      	// 8방향
        let dx = [1, 1, 1, 0, 0, -1, -1, -1];
        let dy = [1, 0, -1, -1, 1, 1, 0, -1];
        for (let i = 0; i < trees.length; i++) {
            const [x, y, age, isLive] = trees[i];
          	// 나이가 5의 배수인 나무만.
            if (age % 5 === 0) {
                for (let j = 0; j < dx.length; j++) {
                    const nextX = x + dx[j] - 1;
                    const nextY = y + dy[j] - 1;
                  	// MAP 을 벗어나지 않게.
                    if (nextX < 0 || nextX >= N ||nextY < 0 || nextY >= N) continue;
                  	// 새 나무 추가.
                    trees.push([nextX + 1, nextY + 1, 1, true]);
                }
            }
        }
    };
	// 겨울
    const WINTER = () => {
        for (let i = 0; i < N; i++) {
          	// 양분 추가.
            for (let j = 0; j < N; j++) {
                MAP[i][j] += R2D2[i][j];
            }
        }
    };
	// 메인 함수.
    const solution = () => {
      	// 1년이 가는것을 카운트
        let cnt = 0;
        while (K > cnt) {
          	// 만약 트리 배열이 있다면
            if (trees.length) {
                SPRING();
                SUMMER();
                AUTUMN();
                WINTER();
              // 트리 배열이 비어있다면, 반복문 즉시 종료.
            }else break;
            cnt++;
        }
        return trees.length;
    };
    console.log(solution());

🧐 후기

최근 구현 문제를 풀고 있는데 구현 문제를 풀 때는 처음 접근 자체가 좀 핵심인 것 같은데, 아직 많이 부족한 것 같다.