코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
알고리즘 분류
- 시뮬레이션
문제 풀이 방법
나무 성장, 번식, 제초제 선택 ~ 뿌리는 과정을 각각 함수로 만들어서 풀이했습니다.
- 코드를 공개하기에 살짝 부끄러운 함수명들로 만들었습니다.
- 나무 성장:
grow() - 번식:
bunsik()(분식 아님,,) - 제초제 과정:
jechoje()
- 나무 성장:
주의해야 할 점
제초제를 뿌리는 범위를 주의해야 합니다.
- 나무가 없는 곳이라면 모두 제초제를 뿌릴 수 있는 후보군이 됩니다.
- 나무가 있는 곳: 4개의 대각선 방향으로 k칸 만큼 전파
- 전파 도중 벽이 있거나 나무가 아예 없는 칸이 있는 경우, 그 칸 까지는 제초제가 뿌려지며 그 이후 칸으로는 제초제가 전파되지 않습니다.
- 나무가 없는 곳: 해당 지점만 제조체를 뿌리고 끝
- 나무가 있는 곳: 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());
}
}느낀점
- 풀이를 보니까 제 풀이보다 간단하던데, 풀이를 보고 제껄로 만들어야겠습니다...
- 요즘 시뮬레이션 문제가 잘 안 풀려서 그나마 쉬운 문제를 풀었는데도, 시간이 너무 많이 걸렸네요... 흑흑... 정신 똑띠 차리고 문제를 풀어야 될 것 같습니다 !!!
- 흑흑,,,, 정신 차리고 화이팅 !!!!!!!!!!!!!!!!!!!!! ㅜ ㅜ