[JAVA] 나무박멸

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

 

알고리즘 분류

• 시뮬레이션

 

문제 풀이 방법

나무 성장, 번식, 제초제 선택 ~ 뿌리는 과정을 각각 함수로 만들어서 풀이했습니다.

• 코드를 공개하기에 살짝 부끄러운 함수명들로 만들었습니다.
  • 나무 성장: grow()
  • 번식: bunsik() (분식 아님,,)
  • 제초제 과정: jechoje()

 

주의해야 할 점

제초제를 뿌리는 범위를 주의해야 합니다.

• 나무가 없는 곳이라면 모두 제초제를 뿌릴 수 있는 후보군이 됩니다.
  • 나무가 있는 곳: 4개의 대각선 방향으로 k칸 만큼 전파
    • 전파 도중 벽이 있거나 나무가 아예 없는 칸이 있는 경우, 그 칸 까지는 제초제가 뿌려지며 그 이후 칸으로는 제초제가 전파되지 않습니다.
  • 나무가 없는 곳: 해당 지점만 제조체를 뿌리고 끝

제가 생각하기에 조심해야 될 부분 2가지에 강조 표시를 했습니다. 이 조건에서 하나라도 맞지 않을 시 오답이므로 주의해서 구현해야 될 것 같습니다.

 

코드

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

public class 나무박멸 {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
    static class Info {
        int tree, jechoje;
        boolean canGrow;

        public Info(int tree) {
            super();
            this.tree = tree;
        }
    }
    static Info map[][];
    static int K, C, totalTree, result;
    static int dr[] = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int dc[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    static Queue<Point> queue = new LinkedList<Point>();
    static int dir[] = new int[8], tmp[] = new int[8];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = stoi(st); // 격자의 크기
        int M = stoi(st); // 년 수
        K = stoi(st); // 확산 범위
        C = stoi(st); // 제초제가 남아있는 년수

        map = new Info[N][N];

        for(int r = 0; r < map.length; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c = 0; c < map[0].length; c++) {
                map[r][c] = new Info(stoi(st));
            }
        }

        while(M-- > 0) {
            grow();
            bunsik();
            jechoje();
            reset();
        }

        System.out.println(result);
    }

    private static void jechoje() {

        Point jechoje = new Point(-1, -1);

        int max = Integer.MIN_VALUE;

        for(int r = 0; r < map.length; r++) {
            for(int c = 0; c < map[0].length; c++) {
                if(map[r][c].jechoje > 0) map[r][c].jechoje--;
                if(map[r][c].tree < 0) continue;

                int cnt = map[r][c].tree;

                if(map[r][c].tree == 0) {
                    if(max < cnt) Arrays.fill(dir, 0);
                } else {
                    for(int d = 0; d < 8; d += 2) {
                        int len = 0;
                        int nr = r;
                        int nc = c;

                        while(true) {
                            nr += dr[d];
                            nc += dc[d];
                            len += 1;

                            if(!check(nr, nc)) {
                                len--;
                                break;
                            }
                            if(map[nr][nc].tree == -1 || map[nr][nc].tree == 0) {
                                break;
                            }
                            if(map[nr][nc].tree > 0) cnt += map[nr][nc].tree;
                            if(len == K) break;
                        }
                        tmp[d] = len;
                    }
                }

                if(max < cnt) {
                    max = cnt;
                    dir = Arrays.copyOf(tmp, tmp.length);
                    jechoje.r = r;
                    jechoje.c = c;
                }
            }
        }

        result += map[jechoje.r][jechoje.c].tree;

        map[jechoje.r][jechoje.c].tree = 0;
        map[jechoje.r][jechoje.c].jechoje = C;

        for(int d = 0; d < 8; d += 2) {
            int len = 0; 

            int nr = jechoje.r;
            int nc = jechoje.c;

            while(len++ < dir[d]) {
                nr += dr[d];
                nc += dc[d];

                if(!check(nr, nc)) continue;

                if(map[nr][nc].tree == -1) break;
                if(map[nr][nc].tree >= 0) {
                    result += map[nr][nc].tree;
                    map[nr][nc].tree = 0;
                    map[nr][nc].jechoje = C;
                }
            }
        }
    }

    private static void reset() {
        for(int r = 0; r < map.length; r++) {
            for(int c = 0; c < map[0].length; c++) {
                map[r][c].canGrow = false;
            }
        }
    }

    private static void bunsik() {
        for(int r = 0; r < map.length; r++) {
            for(int c = 0; c < map[0].length; c++) {

                // 기존에 나무가 있는 곳에서 번식
                if(map[r][c].tree <= 0) continue;

                for(int d = 1; d < 8; d+= 2) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];

                    if(!check(nr, nc)) continue;

                    // 번식이 가능한 곳
                    if(map[nr][nc].jechoje == 0 && map[nr][nc].tree == 0) {
                        map[nr][nc].canGrow = true;
                    }
                }

                queue.add(new Point(r, c));
            }
        }

        while(!queue.isEmpty()) {
            Point current = queue.poll();

            int cnt = 0;

            for(int d = 1; d < 8; d += 2) {
                int nr = current.r + dr[d];
                int nc = current.c + dc[d];

                if(!check(nr, nc)) continue;
                if(map[nr][nc].canGrow) cnt++;
            }

            for(int d = 1; d < 8; d += 2) {
                int nr = current.r + dr[d];
                int nc = current.c + dc[d];

                if(!check(nr, nc)) continue;
                if(map[nr][nc].canGrow) map[nr][nc].tree += map[current.r][current.c].tree / cnt;
            }
        }
    }

    private static void grow() {
        for(int r = 0; r < map.length; r++) {
            for(int c = 0; c < map[0].length; c++) {
                // 나무가 없는 칸
                if(map[r][c].tree <= 0) continue;
                int cnt = 0;

                for(int d = 1; d < 8; d += 2) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];

                    if(!check(nr, nc)) continue;
                    // 인접한 칸 중에서 나무가 있는 칸 수만큼 성장
                    if(map[nr][nc].tree > 0) cnt++;
                }

                map[r][c].tree += cnt;
            }
        }
    }

    private static boolean check(int nr, int nc) {
        return nr >= 0 && nr < map.length && nc >= 0 && nc < map[0].length;
    }

    private static int stoi(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }
}

 

느낀점

• 풀이를 보니까 제 풀이보다 간단하던데, 풀이를 보고 제껄로 만들어야겠습니다...
• 요즘 시뮬레이션 문제가 잘 안 풀려서 그나마 쉬운 문제를 풀었는데도, 시간이 너무 많이 걸렸네요... 흑흑... 정신 똑띠 차리고 문제를 풀어야 될 것 같습니다 !!!
• 흑흑,,,, 정신 차리고 화이팅 !!!!!!!!!!!!!!!!!!!!! ㅜ ㅜ