728x90
https://www.acmicpc.net/problem/16235
살아 있는 나무의 정보를 넣을 디큐 1
죽은 나무 정보 큐 1
겨울에 보충될 양분 배열 1
현재 양분 배열 1
x,y 배열 각 1개씩
선언하여 문제를 풀었다.
주의할 점은 같은 공간의 나무들중에 가장 나이가 어린 나무 먼저 양분을 흡수 하는 것인데,
이를 위해서 Collections.sort 로 정렬을 하게되면 시간초과가 발생한다.
따라서 Deque의 addFirst로 번식된 나무를 제일 앞으로 넣어준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int[][] arr;
static int[][] A;
static Deque<Tree> q;
static Queue<Tree> deadQ;
static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
static class Tree {
int x;
int y;
int old;
Tree(int x, int y, int old) {
this.x = x;
this.y = y;
this.old = old;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
arr = new int[N + 1][N + 1];
A = new int[N + 1][N + 1];
q = new LinkedList<>();
deadQ = new LinkedList<>();
for (int i = 1; i < N + 1; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < N + 1; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
arr[i][j] = 5;
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int old = Integer.parseInt(st.nextToken());
q.add(new Tree(r, c, old));
}
int count = M;
while (K-- > 0) {
// 봄
int tempC = count;
while (tempC-- > 0) {
Tree t = q.poll();
if (arr[t.x][t.y] >= t.old) {
arr[t.x][t.y] -= t.old;
t.old += 1;
q.add(t);
} else {
deadQ.add(t);
count--;
}
}
// 여름
while (!deadQ.isEmpty()) {
Tree t = deadQ.poll();
arr[t.x][t.y] += t.old / 2;
}
// 가을
tempC = count;
Queue<Tree> tempQ = new LinkedList<>();
for (Tree t : q) {
if (t.old % 5 == 0) {
tempQ.add(t);
}
}
while (!tempQ.isEmpty()) {
Tree t = tempQ.poll();
for (int i = 0; i < 8; i++) {
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if (xx > 0 && yy > 0 && xx < N + 1 && yy < N + 1) {
q.addFirst(new Tree(xx, yy, 1));
count++;
}
}
}
// 겨울
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
arr[i][j] += A[i][j];
}
}
}
System.out.println(count);
}
}
'Java' 카테고리의 다른 글
[백준 21608] 상어 초등학교 (JAVA) (0) | 2023.04.05 |
---|---|
[백준 15683] 감시 (JAVA) (0) | 2023.04.05 |
[백준 9466] 텀 프로젝트 (JAVA) (0) | 2023.04.03 |
[백준 1107] 리모컨 (JAVA) (0) | 2023.03.29 |
[백준 7569] 토마토 (JAVA) (0) | 2023.03.28 |