[CodeTree/Java] 나무박멸

[CodeTree/Java] 나무박멸

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

---

문제 해석

이 문제에서는 n*n 격자 위에서 나무가 번식하고 제초제를 통해 그 성장을 억제하는 시뮬레이션을 진행한다. 주어진 입력은 격자의 크기 n, 시뮬레이션을 진행할 년 수 m, 제초제의 확산 범위 k, 제초제의 지속 시간 c로 구성된다. 각 격자 칸은 나무의 수, 빈 칸, 또는 벽으로 표시된다. 나무는 인접한 칸으로 성장하고 번식할 수 있으며, 제초제는 대각선 방향으로 k칸 만큼 확산되어 나무를 박멸한다. 제초제는 벽을 만나면 확산이 중단된다.

풀이 과정

1. 성장: 모든 나무는 인접한 네 칸 중 나무가 있는 칸의 수만큼 성장한다. 이 과정은 모든 나무에 동시에 적용된다.
2. 번식: 기존 나무는 인접한 네 칸 중 빈 칸에 번식을 시도한다. 번식 가능한 칸의 수에 따라 나무 그루 수가 나누어지며, 나머지는 버린다.
3. 제초제 활용: 제초제는 나무가 가장 많이 박멸되는 칸에 뿌려진다. 제초제가 뿌려진 칸과 대각선 k칸 범위 내 나무는 모두 박멸된다. 벽을 만나면 확산이 멈춘다.
4. 박멸 결과: 모든 과정을 m년 동안 반복하여 총 박멸한 나무의 수를 계산한다.

코드

package edu.ssafy.im.CodeTree.treeKillAll;

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

public class Main {
    // 격자의 크기 N, 시뮬레이션 년 수 M, 제초제 확산 범위 K, 제초제 지속 시간 C
    private static int N, M, K, C;
    private static int[][] map, copyMap, visited; // 각각 현재 나무 상태, 복제 나무 상태, 제초제 방문 상태를 저장
    private static final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 상하좌우 이동을 위한 방향 배열
    private static final int[][] diagonal = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}; // 대각선 이동을 위한 방향 배열
    private static int ans = 0; // 전체 제초제로 박멸된 나무의 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력을 통해 파라미터 초기화
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        // 격자 정보 입력
        map = new int[N][N];
        copyMap = new int[N][N];
        visited = new int[N][N];
        for (int x = 0; x < N; x++) {
            st = new StringTokenizer(br.readLine());
            for (int y = 0; y < N; y++) {
                map[x][y] = Integer.parseInt(st.nextToken());
            }
        }

        sb.append(sol());
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    // 제초제 지속시간 갱신 및 처리
    private static void updateVisited() {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (visited[x][y] > 0) visited[x][y]--; // 제초제 카운트 다운
                else if (map[x][y] == -2) map[x][y] = 0; // 제초제 만료 시 칸 초기화
            }
        }
    }

    // 주어진 년도만큼 성장, 번식, 제초제 처리 반복
    private static int sol() {
        for (int m = 0; m < M; m++) {
            updateVisited();
            grow();
            breed();
            kill();
        }
        return ans;
    }

    // 최대 박멸 지점 찾고 제초제 확산
    private static void kill() {
        Tree tree = findMax();
        if (tree.x != -1) spread(tree);
    }

    // 제초제 확산 처리
    private static void spread(Tree tree) {
        map[tree.x][tree.y] = -2;
        visited[tree.x][tree.y] = C;
        for (int[] d : diagonal) {
            for (int k = 1; k <= K; k++) {
                int nx = tree.x + d[0] * k;
                int ny = tree.y + d[1] * k;

                if (checkRange(nx, ny)) break;
                if (map[nx][ny] == -1) break;
                int tmp = map[nx][ny];
                map[nx][ny] = -2;
                visited[nx][ny] = C;
                if (tmp == 0 || tmp == -2) break;
            }
        }
    }

    // 제초제를 뿌릴 위치 선정 (최대 박멸 지점 찾기)
    private static Tree findMax() {
        int rs = 0, rx = -1, ry = -1;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (map[x][y] <= 0) continue; // 나무가 없거나 벽인 경우 무시
                int sum = map[x][y];
                for (int[] d : diagonal) {
                    for (int k = 1; k <= K; k++) {
                        int nx = x + d[0] * k;
                        int ny = y + d[1] * k;

                        if (checkRange(nx, ny) || map[nx][ny] <= 0) break; // 범위 밖이거나 나무가 없는 경우 중단
                        sum += map[nx][ny];
                    }
                }
                // 조건 만족 시 최대값 갱신
                if (sum < rs || (sum == rs && x > rx) || (sum == rs && x == rx && y > ry)) continue;
                rs = sum;
                rx = x;
                ry = y;
            }
        }

        ans += rs; // 박멸된 나무 수 추가
        return new Tree(rx, ry); // 박멸 시작 위치 반환
    }

    // 나무 번식 처리
    private static void breed() {
        copy(); // 현재 상태 복제

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (map[x][y] <= 0) continue; // 나무가 없거나 벽인 경우 무시

                int count = 0;
                for (int[] d : direction) {
                    int nx = x + d[0];
                    int ny = y + d[1];

                    if (checkRange(nx, ny)) continue; // 범위 밖이면 무시
                    if (map[nx][ny] == 0) count++; // 번식 가능한 빈 칸 세기
                }

                if (count == 0) continue; // 번식할 곳이 없으면 넘어감
                int newTree = map[x][y] / count; // 나무 그루 수 나누기

                for (int[] d : direction) {
                    int nx = x + d[0];
                    int ny = y + d[1];

                    if (checkRange(nx, ny)) continue; // 범위 밖이면 무시
                    if (map[nx][ny] == 0) { // 번식 가능한 경우
                        copyMap[nx][ny] += newTree; // 복제된 맵에 추가
                    }
                }
            }
        }

        paste(); // 복제된 상태를 원본에 반영
    }

    // 복제된 상태를 원본에 반영
    private static void paste() {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                map[x][y] = copyMap[x][y];
            }
        }
    }

    // 원본 상태를 복제
    private static void copy() {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                copyMap[x][y] = map[x][y];
            }
        }
    }

    // 나무 성장 처리
    private static void grow() {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (map[x][y] <= 0) continue; // 나무가 없거나 벽인 경우 무시
                int count = 0;
                for (int[] d : direction) {
                    int nx = x + d[0];
                    int ny = y + d[1];

                    if (checkRange(nx, ny)) continue; // 범위 밖이면 무시
                    if (map[nx][ny] > 0) count++; // 성장할 수 있는 나무 카운트
                }
                map[x][y] += count; // 성장
            }
        }
    }

    // 범위 체크
    private static boolean checkRange(int x, int y) {
        return 0 > x || x >= N || 0 > y || y >= N; // 격자 범위를 벗어나는지 검사
    }

    // 나무 정보를 저장하기 위한 내부 클래스
    static class Tree {
        int x, y;

        public Tree(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

시간 복잡도 분석

• 각 함수는 모든 격자 칸 𝑁×𝑁을 순회하고, 각 칸에서 주변 칸을 추가로 검사한다. 이 때, 제초제 확산은 대각선 방향으로 최대 𝐾칸을 검사한다.
• 전체 시간 복잡도는 각 함수에서 𝑂(𝑁^2) 및 𝑂(𝑁^2𝐾)이고, 전체 프로세스를 𝑀년 동안 반복하므로 𝑂(𝑀×𝑁^2𝐾)가 된다.

느낀점

이 문제를 풀면서 시뮬레이션 문제에 대한 처리 기법과 배열을 사용하는 방법을 배웠다. 특히, 제초제가 확산되는 로직은 구현하기 흥미로웠다. 다양한 조건과 예외 사항을 처리하면서 로직의 정확성을 보장하는 방법을 배울 수 있었다. 이러한 문제는 실제 시스템을 모델링하는 데 있어서도 유용하며, 알고리즘과 프로그래밍 능력을 향상시키는 데 도움이 되었다.