나무박멸[G4]

https://csg1353.tistory.com/51

 

이전에 틀렸던 문제를 연습차 다시 풀이하였다.

 

코드

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

public class Main {
       static int N, M, K, C;
   static int[][] map;
   static int[][] jecho;
   static int answer;
   static Queue<Pos> tempQ = new ArrayDeque<>();
   static Queue<Pos> treeQ = new ArrayDeque<>();
   static final int[] DR = {-1, 0, 1, 0};
   static final int[] DC = {0, 1, 0, -1};
   static final int[] DCR = {-1, -1, 1, 1}; //좌상 / 우상 / 좌하 / 우하
   static final int[] DCC = {-1, 1, -1, 1}; //대각선 살포용

    public static void main(String[] args) throws Exception {
              input();
      while(M-- > 0) {
         grow();
         spread();
         Pos result = target();
         remove(result); //제초제 살포
         minus(); //제초제 1년 감소
      }
      System.out.println(answer);
    }

     public static void grow() {
      for(int r = 0; r < N; r++) {
         for(int c = 0; c < N; c++) {
            if(map[r][c] <= 0) continue; 
            int cnt = 0;
            for(int k = 0; k < 4; k++) {
               int nr = r + DR[k];
               int nc = c + DC[k];
               if(cantGo(nr, nc)) continue;
               if(map[nr][nc] > 0) cnt++;
            }
            map[r][c] += cnt; //자기자신 성장
         }
      }
   }
   
   public static void spread() {
      //인접한 4칸 번식, 제초제가 있는지 맵밖인지 벽인지 확인
      for(int r = 0; r < N; r++) {
         for(int c = 0; c < N; c++) {
            if(map[r][c] <= 0) continue;
            int cnt = 0; //인접칸
            for(int k = 0; k < 4; k++) {
               int nr = r + DR[k];
               int nc = c + DC[k];
               if(cantGo(nr, nc) || map[nr][nc] != 0 || jecho[nr][nc] > 0) continue;
               cnt++;
               tempQ.add(new Pos(nr, nc));
            }
            
            while(!tempQ.isEmpty()) {
               Pos now = tempQ.poll();
               now.value = map[r][c] / cnt;
               treeQ.add(now);
            }
         }
      }
      
      //번식
      while(!treeQ.isEmpty()) {
         Pos now = treeQ.poll();
         map[now.r][now.c] += now.value;
      }
   }
   
   public static Pos target() {
      Pos result = new Pos(0, 0, 0); //제초제 스팟
      for(int r = 0; r < N; r++) {
         for(int c = 0; c < N; c++) {
            checkTarget(r, c, result); //각 스팟 별 체크
         }
      }
      
      return result;
   }
   
  public static void checkTarget(int r, int c, Pos result) {
      //r c에서 대각선으로 K칸까지 박멸 발생
      int res = Math.max(map[r][c], 0); //0 이상 현재 위치 값 기본
      int nr, nc;
      if(map[r][c] <= 0) return;
      
	  for(int j = 0; j < 4; j++) {
          for(int i = 1; i <= K; i++) {
             nr = r + (DCR[j] * i); 
             nc = c + (DCC[j] * i);
             if(cantGo(nr, nc)) break;
             res += Math.max(map[nr][nc], 0);
             if(map[nr][nc] <= 0 || jecho[nr][nc] > 0) break;
          }
	  }

//	  System.out.println(r + " " + c + " " + res);
      if(res > result.value || 
            (res == result.value && r < result.r) || //결과가 같은데 행이 작음 
            (res == result.value && r == result.r && c < result.c)) {  //결과 및 행 같으면 열 작음
         result.r = r;
         result.c = c;
         result.value = res;

      }
   }

   static void remove(Pos result) {
      int nr, nc;
      int r = result.r; int c = result.c;
      //r c부터 제초제 살포 시작
      tempQ.add(new Pos(r, c, C + 1)); //jecho
      

	  for(int j = 0; j < 4; j++) {
          for(int i = 1; i <= K; i++) {
             nr = r + (DCR[j] * i); 
             nc = c + (DCC[j] * i); 
             if(cantGo(nr, nc)) break;
           	 tempQ.add(new Pos(nr, nc, C + 1)); //jecho
           	if(map[nr][nc] <= 0 || jecho[nr][nc] > 0) break;
              }
	  }
   
      
      while(!tempQ.isEmpty()) {
    	  Pos now = tempQ.poll();
    	  jecho[now.r][now.c] = now.value;
//    	  System.out.println(now.r + " " + now.c);
      }
      
   }
   
   static void minus() {
      for(int i = 0; i < N; i++) {
         for(int j = 0; j < N; j++) {
            if(jecho[i][j] > 0) {
            	jecho[i][j] -= 1;
                if(map[i][j] > 0) { //나무 있을 경우
                	answer += map[i][j];
                	map[i][j] = 0; //제초제
                }
            }
         }
      }
   }
   
   static boolean cantGo(int r, int c) {
      if(r < 0 || c < 0 || r >= N || c >= N) return true;
      return false;
   }
   public static void input() 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());
      K = Integer.parseInt(st.nextToken());
      C = Integer.parseInt(st.nextToken());
      map = new int[N][N];
      jecho = new int[N][N];
      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());
         }
      }
   }
}

class Pos {
   int r, c, value;
   public Pos(int r, int c, int value) {
      this.r = r;
      this.c = c;
      this.value = value;
   }
   
   public Pos(int r, int c) {
      this.r = r;
      this.c = c;
   }
}