[PS] 코드트리 나무 타이쿤 java 풀이

https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon/description?page=3&pageSize=10

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 접근

구현, 시뮬레이션 문제입니다.

특수 영양제 규칙을 준수하여, 크게 특수 영양제 이동 -> 성장 -> 자르기로 로직을 분류합니다.

 

특수 영양제 규칙

1. 영양제는 매년 주어진 규칙에 따라 이동하며, 이동한 칸의 리브로수를 성장시킵니다.
2. 대각선 방향에 높이가 1 이상인 리브로수의 개수만큼 추가로 성장합니다.
3. 이미 영양제를 투입한 칸을 제외한, 높이가 2 이상인 칸은 영양제를 새로 생성하고 높이를 2만큼 줄입니다.

이동 규칙 구현: 범위 벗어나면 반대 편으로 돌아오기

            // 1. 이동
            int[][] nextPlanted = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (planted[i][j] == 1) {
                        int nextRow = (i + dir[d][0] * p % N + N) % N;
                        int nextCol = (j + dir[d][1] * p % N + N) % N;
                        nextPlanted[nextRow][nextCol] = 1;
                    }
                }
            }
            planted = nextPlanted;

이 돌아오는걸 어떻게 해야 하나.. 찾아봐서 겨우 이해했습니다.

 

일단 Java에서 % 연산자는 나머지 연산자로 동작하며, 음수를 포함한 피연산자의 부호를 유지합니다

-1 % 7의 계산 과정

1. 나머지 연산 규칙:
   • Java의 나머지 연산자는 피연산자 중 첫 번째(피제수)의 부호를 유지합니다.
   • 따라서, -1 % 7의 결과는 음수로 유지됩니다.
2. 나머지 연산 계산:
   • -1을 7로 나눕니다. 몫은 0이고 나머지는 -1입니다.
   • 몫: -1 ÷ 7 = 0 (버림 연산, 정수 몫 계산)
   • 나머지: -1 - (7 × 0) = -1

이 문제에서 범위를 벗어나면 반대편 인덱스로 이동하는 코드는 다음과 같습니다.

int nextRow = (i + dir[d][0] * p % N + N) % N;
int nextCol = (j + dir[d][1] * p % N + N) % N;

 

• i는 현재 row, j는 현재 col, dir [d][0]은 현재 연도의 이동해야 하는 방향의 행, p는 몇 칸 가야 하는지, N은 배열 크기입니다.
• (i + dir[d][0] * p) 현재 위치에서 가야 하는 방향을 P만큼 이동한 뒤
• + N으로 음수 방지를 위한 보정을 하고,
• % N으로 격자의 크기를 넘어가지 않도록 제한.

 

예를 들어 j = 0, dir[d][1] = −1, p = 3, j = 0, N= 5일 경우

 

• nextCol=(0+(−1)×3%5+5)%5
• nextCol=(0−3+5)%5=2
• 결과: nextCol=2 (왼쪽으로 세 칸 이동 후 반대편으로 돌아옴).

이후 성장, 자르기 등 남은 과정은 코드로 보는 게 더 이해가 좋을 겁니다.

코드

 

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

public class Main {
    static int[][] dir = {
        {0, 1},    // → (1)
        {-1, 1},   // ↗ (2)
        {-1, 0},   // ↑ (3)
        {-1, -1},  // ↖ (4)
        {0, -1},   // ← (5)
        {1, -1},   // ↙ (6)
        {1, 0},    // ↓ (7)
        {1, 1}     // ↘ (8)
    };
    static int[][] growList = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
    static int N, M;
    static int[][] map;
    static int[][] planted;

    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());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        planted = new int[N][N];

        // 초기 특수 영양제 위치 설정
        planted[N - 1][0] = 1;
        planted[N - 1][1] = 1;
        planted[N - 2][0] = 1;
        planted[N - 2][1] = 1;

        // 리브로수 높이 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 이동 규칙 입력
        int[][] moves = new int[M][2];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            moves[i][0] = Integer.parseInt(st.nextToken()) - 1;
            moves[i][1] = Integer.parseInt(st.nextToken());
        }

        // 시뮬레이션 시작
        for (int t = 0; t < M; t++) {
            int d = moves[t][0];
            int p = moves[t][1];

            // 1. 이동
            int[][] nextPlanted = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (planted[i][j] == 1) {
                        int nextRow = (i + dir[d][0] * p % N + N) % N;
                        int nextCol = (j + dir[d][1] * p % N + N) % N;
                        nextPlanted[nextRow][nextCol] = 1;
                    }
                }
            }
            planted = nextPlanted;

            // 2. 영양제 투입 및 성장
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (planted[i][j] == 1) {
                        map[i][j] += 1;
                    }
                }
            }

            // 3. 대각선 성장
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (planted[i][j] == 1) {
                        int cnt = 0;
                        for (int[] near : growList) {
                            int nextRow = i + near[0];
                            int nextCol = j + near[1];
                            if (0 <= nextRow && nextRow < N && 0 <= nextCol && nextCol < N) {
                                if (map[nextRow][nextCol] > 0) {
                                    cnt++;
                                }
                            }
                        }
                        map[i][j] += cnt;
                    }
                }
            }

            // 4. 새로운 영양제 생성 및 기존 영양제 제거
            int[][] newPlanted = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (planted[i][j] == 1) {
                        planted[i][j] = 0; // 기존 영양제 제거
                    } else if (map[i][j] >= 2) {
                        map[i][j] -= 2;
                        newPlanted[i][j] = 1; // 새로운 영양제 생성
                    }
                }
            }
            planted = newPlanted;
        }

        // 리브로수 높이의 합 계산
        int answer = 0;
        for (int[] row : map) {
            for (int h : row) {
                answer += h;
            }
        }
        System.out.println(answer);
    }
}