[ 백준 ] 27942 :danceplant:

📌 Problem

N x N (N은 짝수) 크기의 무대 정중앙에 2 x 2 크기의 식물이 있다. 식물은 다음과 같이 춤을 춘다. 식물의 상하좌우와 맞닿은 면적 중 가장 큰 에너지 합을 가진 변으로 늘어난다. 춤을 출 때는 맞닿은 변의 에너지를 흡수하며 늘어난다. 더는 늘어날 수 없거나 섭취 가능한 에너지가 0 이하이면 춤을 멈춘다. 총 에너지 섭취량과 춤추는 방향 기록을 출력하면 된다. 방향은 상하좌우가 UDLR으로 나타낸다. 추가로 섭취 가능한 에너지가 동일할 때는 상하좌우 순으로 우선순위를 둔다.

📌 Solution

매순간마다 상하좌우와 맞닿은 면의 에너지 총량을 구하고 가장 큰 에너지하을 가진 방향으로 이동한다. 만약 최대 에너지 총량이 0이거나 더는 이동할 수 없다면 종료한다.

📌 Code

// Input : Read size information
int N = Integer.parseInt(reader.readLine());    // Size of dancing stage
int[][] stage = new int[N][N];                  // Energies of stage

// Input : Read energy information
StringTokenizer tokenizer;
for (int r = 0; r < N; r++) {
    tokenizer = new StringTokenizer(reader.readLine());
    for (int c = 0; c < N; c++) {
        stage[r][c] = Integer.parseInt(tokenizer.nextToken());
    }
}

// Dancing Plant
DancePlant dancePlant = new DancePlant(N, stage);

// Plant dances and save moving histories (UDLR)
StringBuilder history = new StringBuilder();
while (true) {
    char direction = dancePlant.dance();
    if (direction == ' ') break;
    history.append(direction);
}

// Output : Print Energy eaten end history
result.append(dancePlant.getEnergy()).append('\n').append(history);

class DancePlant {

    private int sr, sc, er, ec;     // startRow, startCol, endRow, endCol
    private final int[][] stage;    // Energy information
    private int energy;             // Total energy eaten

    private final char[] chars = {'U', 'D', 'L', 'R'};

    public DancePlant(int size, int[][] stage) {
        this.stage = stage;
        sr = sc = size / 2 - 1;
        er = ec = size / 2;
    }

    /**
     * Dance one time
     * @return Dancing direction
     */
    public char dance() {
        int maxEnergy = 0;
        char direction = ' ';
        for (int dir = 0; dir < 4; dir++) {
            int sum = sideSum(dir);
            if (sum > maxEnergy) {
                maxEnergy = sum;
                direction = chars[dir];
            }
        }

        energy += maxEnergy;
        switch (direction) {
            case 'U' -> sr--;
            case 'D' -> er++;
            case 'L' -> sc--;
            case 'R' -> ec++;
        }

        return direction;
    }

    /**
     * Check side energy summation
     * @param dir 0 U, 1 D, 2 L, 3 R
     * @return Summation of energy
     */
    private int sideSum(int dir) {
        return switch (dir) {
            case 0 -> sum(sc, ec, sr - 1, true);
            case 1 -> sum(sc, ec, er + 1, true);
            case 2 -> sum(sr, er, sc - 1, false);
            case 3 -> sum(sr, er, ec + 1, false);
            default -> throw new IllegalArgumentException("Should not reach here");
        };
    }

    /**
     * Calculate total energy of one side
     * @param from Range from info
     * @param to Range to info
     * @param base Fixed info
     * @param vertical Moving direction (true UD, false LR)
     * @return Summation of one side energy
     */
    private int sum(int from, int to, int base, boolean vertical) {
        try {
            int sum = 0;
            for (int i = from; i <= to; i++)
                sum += stage[vertical ? base : i][vertical ? i : base];
            return sum;
        } catch (ArrayIndexOutOfBoundsException e) {
            return 0;
        }
    }

    public int getEnergy() {
        return energy;
    }
}