💻 문제
- 삼성 SW 역량테스트 2022 상반기 오후 2번 문제
- 시뮬레이션
🔐 풀이
- 시간: 2시간 + a
아이디어
문제 그대로를 구현하면 되는 시뮬레이션 문제이다. 그중에서 제초제 뿌린 구역을 어떻게 관리하할지가 핵심이었다.
"제초제가 뿌려진 곳에 다시 제초제가 뿌려지는 경우에는 새로 뿌려진 해로부터 다시 c년동안 제초제가 유지됩니다."라는 말이 있어서 visited 배열을 boolean에서 int로 바꿔주었다. c+1번 째에 제초제가 갱신되므로 값에 c+1을 넣어주었다. int로 관리함으로써 테스트케이스 7번을 마침내 통과할 수 있었다.
추가로 테스트케이스 5번에서 런타임에러를 받았는데, 이는 제초제를 뿌릴 곳이 없을 때 특정 인덱스의 값을 불러오려고 해서 발생한 문제였다.
시간복잡도
성장/번식/제초제 뿌리는 과정이 각각 N^2이고 이를 M년 만큼 수행한다
O(M * N^2)👉 제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, -1, 0, 1};
static int[] ddx = {-1, -1, 1, 1};
static int[] ddy = {-1, 1, -1, 1};
static class Pos implements Comparable<Pos>{
int x; int y;
int count;
Pos(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
@Override
public int compareTo(Pos o) {
if (this.count == o.count) {
if (this.x == o.x) {
return this.y - o.y;
}
return this.x - o.x;
}
return o.count - this.count;
}
@Override
public String toString() {
return x + " " + y + " " + count;
}
}
static int n, m, k, c;
static int[][] trees;
static int[][] visited; // 제초제 기록을 상수로ㅠㅠㅠㅠㅠ
static List<Pos> candidates;
static int ans;
public static void main(String[] args) throws IOException {
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());
trees = new int[n][n];
visited = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
trees[i][j] = Integer.parseInt(st.nextToken());
}
}
while (m-->0) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] > 0) visited[i][j]--;
}
}
candidates = new ArrayList<Pos>();
grow();
breeding();
spray();
}
System.out.println(ans);
}
private static void grow() {
// 4방향 기준 개수 구하기
int[][] tmp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (trees[i][j] == 0 || trees[i][j] == -1 || visited[i][j] != 0) continue;
int count = 0;
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (outOfRange(nx, ny) || visited[nx][ny] != 0) continue;
if (trees[nx][ny] != 0) count++;
}
tmp[i][j] = count;
}
}
// 동시에 성장
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
trees[i][j] += tmp[i][j];
}
}
}
private static void breeding() {
// 벽, 다른 나무, 제초제가 없어야 함
// 번식 가능한 곳 개수만큼 나눈다
int[][] tmp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (trees[i][j] <= 0) continue;
int count = 0; // 번식이 가능한 칸의 개수
List<int[]> pos = new ArrayList<>();
for (int d = 0; d < 4; d++) {
int nx = i + dx[d];
int ny = j + dy[d];
if (outOfRange(nx, ny) || trees[nx][ny] != 0 || visited[nx][ny] > 0) continue;
count++;
pos.add(new int[] {nx, ny});
}
for (int[] p : pos) {
tmp[p[0]][p[1]] += trees[i][j]/count;
}
}
}
// 동시에 번식
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
trees[i][j] += tmp[i][j];
}
}
}
private static void spray() {
// 가장 많이 박멸되는 칸에 제초제 뿌림
// 대각선 방향으로 k칸 만큼 + 본인 거
// bfs로 박멸되는 나무 개수 구하기
// 벽, 나무 아예 없는 경우 거기까지만
// c년 만큼 작용
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (trees[i][j] == 0 || trees[i][j] == -1) continue;
int count = trees[i][j];
for (int d = 0; d < 4; d++) {
for (int size = 1; size <= k; size++) {
int nx = i + ddx[d] * size;
int ny = j + ddy[d] * size;
if (outOfRange(nx, ny) || trees[nx][ny] == 0) break;
count += trees[nx][ny];
}
}
candidates.add(new Pos(i, j, count));
}
}
if (candidates.size() == 0) return;
Collections.sort(candidates);
// 제초제 뿌리기
Pos target = candidates.get(0);
ans += target.count;
visited[target.x][target.y] = c+1;
trees[target.x][target.y] = 0;
for (int d = 0; d < 4; d++) {
for (int size = 1; size <= k; size++) {
int nx = target.x + ddx[d] * size;
int ny = target.y + ddy[d] * size;
if (outOfRange(nx, ny)) break;
if (trees[nx][ny] == 0) {
visited[nx][ny] = c+1;
break;
}
visited[nx][ny] = c+1;
trees[nx][ny] = 0;
}
}
}
private static boolean outOfRange(int x, int y) {
return x < 0 || x >= n || y < 0 || y >= n || trees[x][y] == -1;
}
}
's Coding Memory