문제
풀이
전형적인 시뮬레이션 문제이다.
queue를 활용하여 문제를 해결하였다.
늘 느끼는 거지만, 시뮬레이션에는 특별한 기술이나 구상 방법보다는 문제가 요구하는 것을 정확하게 이해하고 구현하는 것이 중요할 것 같다.
코드
import java.util.*;
public class 나무박멸 {
static final int D = 4;
static int N, M, K, C, res;
static int[][] map; //맵
static int[][] del; //제초제 여부
static int[][] board; //시뮬레이션용 보드
static boolean[][] visit;
static int[][] d = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
static int[][] cross = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
static Queue<Tree> q = new ArrayDeque<>();
static Queue<Tree> subQ = new ArrayDeque<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); //크기
M = sc.nextInt(); //진행년도
K = sc.nextInt(); //제초 범위
C = sc.nextInt(); //제조 남아 있는 년도
map = new int[N][N];
del = new int[N][N];
board = new int[N][N];
//맵 입력받기 / 트리 정보 만들어 넣기
for (int i = 0; i < N; i++) {
for(int j = 0; j < N; j ++) {
map[i][j] = sc.nextInt();
}
}
//년도만큼 진행
for (int i = 0; i < M; i++) {
grow(); //나무 성장
make(); //나무 번식
down(); //제초제 주기 1년 감소
search(); //가장 많이 제거되는 칸 찾기 && 제초제 뿌리기
}
System.out.println(res);
}
private static void down() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(del[i][j] > 0) del[i][j] -= 1;
}
}
}
private static void search() {
int max = 0; //최대 제초 값
int mr = 999, mc = 999; //최대 제초되는 인덱스 (r, c)
int now;
// 완전 탐색 시행 : 각 맵마다 제초 범위 찍어보고 최대 값이 있는 좌표 저장
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
now = searchTwo(i, j); //현재 좌표에서 작업했을 때 값 반환
if(max <= now) {//1. 조건에 맞는다면 최대값 및 수치 갱신
if(max == now) {
if(i > mr) continue; //2. 탈락 - 행이 더 높음
if(i == mr && j > mc) continue; //3. 탈락 - 열이 더 높음
}
//아니라면 갱신
max = now; mr = i; mc = j;
}
}
}
//4. 해당 값 넘겨주기
res += max;
//5. 해당 좌표 기준으로 제초제 뿌리기 시행
remove(mr, mc);
}
private static void remove(int r, int c) {
//1. 제초제 투하
del[r][c] = C; // 현재 위치 제초제 투하
// 제초제 확산
if (map[r][c] > 0) {
for (int j = 0; j < D; j++) {
for (int i = 1; i <= K; i++) {
int nr = r + cross[j][0] * i;
int nc = c + cross[j][1] * i;
if (cantGo(nr, nc))
continue;// 인덱스 아웃
del[nr][nc] = C; // 제초제 투하
if (map[nr][nc] <= 0)
break;
}
}
}
//2. 나무 제거
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(del[i][j] > 0 && map[i][j] > 0) map[i][j] = 0;
}
}
}
private static int searchTwo(int r, int c) {
//1. 인자 정비
int remove = 0; //리턴값
clean(); //계산해볼 보드의 내부값 0으로 초기화
//2. 나무가 있다면 최대 가산치 K만큼 확산 가능, 아닐 경우 거기까지만
board[r][c] = C; //현재 위치 제초제 투하
//현재 위치가 나무가 아니라면 해당 위치만 투하하고 끝
if(map[r][c] > 0) {
for (int j = 0; j < D; j++) {
for (int i = 1; i <= K; i++) {
int nr = r + cross[j][0] * i;
int nc = c + cross[j][1] * i;
if(cantGo(nr, nc)) continue;//인덱스 아웃
board[nr][nc] = C; //제초제 투하
if(map[nr][nc] <= 0) break;
}
}
}
//3. board에 저장된 값으로 최대값 계산
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//제초제 있는 칸일 경우,그리고 그 칸에 나무가 있다면
if(board[i][j] > 0 && map[i][j] > 0) remove += map[i][j]; //값 가산
}
}
return remove; //제초되는 수 반환
}
private static void clean() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = 0;
}
}
}
private static void make() {
//번식 진행 : 인접한 4개 칸 중 나무, 제초제 전부 없는 칸 개수 확인 및 해당 칸 queue에 담아 저장
//수치 : 현재 칸 / 번식되는 칸
//1. 일단 완전탐색으로 나무 위치 찾음
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j] > 0) makeTwo(i, j); //2. 찾은 값 넘겨주고 번식 위한 단계 진행
}
}
//3. 큐에 저장된 수치만큼 전부 가산
while(!q.isEmpty()) {
Tree now = q.poll();
map[now.r][now.c] += now.val;
}
}
private static void makeTwo(int r, int c) {
//1. 사방탐색으로 번식이 가능한 칸의 개수를 찾음
int spot = 0; //번식 가능한 칸
for (int i = 0; i < D; i++) {
int nr = r + d[i][0];
int nc = c + d[i][1];
//인덱스 제거, 맵이 빈칸일 경우, 해당 위치에 제초제가 없을 경우
if(cantGo(nr, nc) || map[nr][nc] != 0 || del[nr][nc] != 0) continue;
spot += 1; //위치 증가
subQ.offer(new Tree(nr, nc)); //일단 수치 없이 위치만 저장해놓음
}
//2. 수치 계산 후 이를 메인 큐에 다시 집어넣음. = 해당 저장값은 모든 연산이 끝난 후 일괄 가산
while(!subQ.isEmpty()) {
int val = map[r][c] / spot; //번식할 수치
Tree temp = subQ.poll();
temp.val = val; //번식 수치 넣음
q.offer(temp);
}
}
private static void grow() {
//1. 나무 집어넣기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j] > 0) q.offer(new Tree(i, j, map[i][j])); //트리 정보 넣기
}
}
//2. 큐에서 나무가 없어질 때까지 나무 꺼내기
//꺼낸 나무에서 사방 탐색 진행하여 나이가 얼마나 먹을 지 확인 및 적용
while(!q.isEmpty()) {
Tree now = q.poll();
int age = 0;
for (int i = 0; i < D; i++) {
int nr = now.r + d[i][0];
int nc = now.c + d[i][1];
if(cantGo(nr, nc) || map[nr][nc] <= 0) continue;
age += 1;
}
map[now.r][now.c] += age;
}
}
static boolean cantGo(int r, int c) {
if(r < 0 || c < 0 || r >= N || c >= N) return true;
return false;
}
static class Tree {
int r, c;
int val;
public Tree(int r, int c) {
super();
this.r = r;
this.c = c;
}
public Tree(int r, int c, int val) {
super();
this.r = r;
this.c = c;
this.val = val;
}
}
}
안녕하세요.