[JAVA] 코드트리 나무박멸

https://www.codetree.ai/frequent-problems/tree-kill-all/description

코드트리

 

1. 서론

 

딱히 사용되는 알고리즘 기법은 없고 그냥 빡센 구현(시뮬레이션) 문제다.

 

2. 문제 풀이

 

2차원 배열의 한 칸에 나무그루 수와 벽, 그리고 빈칸이 있다.

이때 초기 나무, 벽, 빈칸이 주어지고 제초제를 뿌리는 칸의 범위인 k, 반복년인 m, 제초제가 남아있는 년 수 c가 주어진다.

 

그리고 이것은 다음과 같은 과정을 반복한다.

 

 

1. 인접한 네 개의 칸 중 나무가 있는 칸의 수만큼 나무가 성장합니다. 성장은 모든 나무에게 동시에 일어납니다.
2. 기존에 있었던 나무들은 인접한 4개의 칸 중 벽, 다른 나무, 제초제 모두 없는 칸에 번식을 진행합니다. 이때 각 칸의 나무그루 수에서 총번 식이 가능한 칸의 개수만큼 나누어진 그루 수만큼 번식이 되며, 나눌 때 생기는 나머지는 버립니다. 번식의 과정은 모든 나무에서 동시에 일어나게 됩니다.
3. 각 칸 중 제초제를 뿌렸을 때 나무가 가장 많이 박멸되는 칸에 제초제를 뿌립니다. 제초제를 뿌릴 때 4개의 대각선 방향으로 k칸만큼 전파되게 됩니다. 단 전파되는 도중 벽이 있거나 나무가 아얘 없는 칸이 있는 경우, 그 칸 까지는 제초제가 뿌려지며 그 이후의 칸으로는 제초제가 전파되지 않습니다. 제초제가 뿌려진 칸에는 c 년만큼 제초제가 남아있다가 c+1년째가 될 때 사라지게 됩니다. 제초제가 뿌려진 곳에 다시 제초제가 뿌려지는 경우에는 새로 뿌려진 해로부터 다시 c년동안 제초제가 유지됩니다.

이 과정을 m 년 반복한 후의 박멸한 나무의 그루 수를 구하는 문제이다.

 

나는 이 문제를 읽고 이렇게 풀이를 구성했다.

 

 

 

---

 

값 입력 받음

0은 빈칸, 그 이상의 숫자는 나무그루 수, -1은 벽

배열 크기 n, 박멸이 진행되는 년수 m, 제초제 확산 범위 k, 제초제가 남아있는 년 수 c

** 이 모든 것은 원래 배열이 아닌 tmp 배열 추가로 만들어서 값 만든 후 값 복사하든 넣든 해줘야 함

전체 m 년 반복

*제초제의 시간을 체크해주는 함수

제초제 배열에 값이 0보다 크면 --해줌 
원래 배열에서 값이 -2인 곳이 있는데 그곳의 제초제 배열 좌표가 0이 됐으면 -2를 다시 0으로 바꿔줌

*성장 함수

배열을 돌다가 배열의 값이 0보다 크면(나무인 경우) 동서남북 나무가 있는지 cnt
그리고 그 배열에 그 cnt 값 더해줌

*번식 함수

배열을 돌다가 나무이면 동서남북으로 빈칸 cnt
그리고 다시 한번 그 자리에서 동서남북 돌면서 빈칸에 (그 자리의 나무 값/번식가능 칸) 넣어줌

*제초제 위치 정하는 함수(방향이 먼저, k칸은 그 안에서)

가장 많이 나무가 박멸되는 칸을 구해야 함
=> 나무가 있는 모든 칸에 제초제를 뿌려서 그 자리에 뿌리면 나무가 몇 그루 죽는지 적기

배열을 돌다 나무 발견
그 칸 기준으로 k칸만큼 대각선 4개 방향에 있는 나무 수 더함 => 빈 배열에 그 칸에 몇 그루 나무가 죽는지 적음

전체 칸 탐색 반복 후 값이 정해진 배열을 돌면서 가장 큰 값의 좌표를 구함
만약 가장 큰 값이 여러 개인 경우, 그것 중 행이 작은 칸, 행도 같으면 열이 작은 칸

즉 값이 가장 큰 것을 구함
그 후 다시 배열을 돌면서 그 값과 같은 값을 가지는 좌표들을 저장
행, 열 순으로 정렬 돌림
가장 위의 값을 좌표로!

=> 이 좌표가 제초제를 뿌릴 칸

*제초제 진짜로 뿌리는 작업을 진행하는 함수

제초제 위치 정하는 함수에서 정해진 좌표에 + 대각선 k칸을 돌면서 그 위치의 값 박멸한 나무그루수에 +로 저장하고 그 자리를 -2로 바꿈

그리고 다른 배열에 그 똑같은 좌표와 대각선 k칸에 c를 넣음

 

---

 

이를 토대로 코드를 짰고, 이후 주어진 테케 2개는 맞았는데 제출했을 때 테케 6,7번에서 틀렸는데 각각 원인은 이거였다.

 

6번의 경우: 더 이상 박멸할 나무가 없는 경우를 생각해주지 않았다.

7번의 경우: 위의 3번 과정에서 "단 전파되는 도중 벽이 있거나 나무가 아예 없는 칸이 있는 경우, 그 칸 까지는 제초제가 뿌려지며 그 이후의 칸으로는 제초제가 전파되지 않습니다." 이 부분을 그 칸까지는 이 아니라 그 칸을 만나면 바로 끝냈는데 그 칸까지 제초제가 뿌려지게 하고 그 다음칸부터 끝내는 것으로 수정했다.

 

7번이야 내가 문제를 자세히 안 읽고 구현을 못해서 그렇다 쳐도 6번은 진짜 그림으로 설명하지 않는 이상은 그냥 떠올리기 어렵다.(에바임 ㅠㅠ)

그래서 6번 같은 경우는 코드를 읽고 읽다가 만약에 터진다면 어디서 터질까? 계속 생각해본 결과 여기서 터질 것 같아서 체크해보니 진짜라서 수정한 경우다.

 

 

 

3. 코드 설명

 

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

public class Main {
	
	static int n, m, k, c, ans;
	static int[][] map, kill, tmp; // 숲, 제초제 위치, 옮길 상자
	static int[] dx = {-1, 1, 0, 0, 1, 1, -1, -1}, dy= { 0, 0, 1, -1, -1, 1, 1, -1}; //동서남북, 대각선4방
	static Point choice;
	
    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()) + 1; //1년은 유지해야 하기 때문에 1을 더해줬다.(그냥 숫자로 적으면 0년차에 같이지워짐)
        
        map = 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());
        }
        
        kill = new int[n][n];
        tmp = new int[n][n];
        
        for (int i = 0; i < m; i++) {
        	check();
        	grow();
        	move();
        	select();
        	if (choice.x == -1) continue;
        	killing();	
        }
        
        System.out.println(ans);
    }
    
    public static void check() {//제초제 체크해주는 함수
    	for (int i = 0; i < n; i++) //제초제 시간 체크
    		for (int j = 0; j < n; j++)
    			if (kill[i][j] > 0)
    				kill[i][j]--;
    	
    	for (int i = 0; i < n; i++) //제초제 유효기간 끝
    		for (int j = 0; j < n; j++)
    			if (map[i][j] == -2 && kill[i][j] == 0)
    				map[i][j] = 0;
    }
    
    public static void grow() { // 나무 성장 함수
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			if (map[i][j] > 0) { //나무인 경우
    				int cnt = 0;
    				for (int p = 0; p < 4; p++) {
    					int nx = i + dx[p], ny = j + dy[p];
    					if (range(nx, ny) && map[nx][ny] > 0)
    						cnt++;
    				}
    				map[i][j] += cnt; 
    			}
    		}
    	}
    }
    
    public static void move() { //나무 번식 함수
    	copy(tmp, map); //값이 오염되는 것을 막기 위해 tmp 사용
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			if (map[i][j] > 0) { //나무인 경우
    				int cnt = 0;
    				for (int p = 0; p < 4; p++) {
    					int nx = i + dx[p], ny = j + dy[p];
    					if (range(nx, ny) && map[nx][ny] == 0) //번식할 수 있는 곳 체크
    						cnt++;
    				}
    				
    				for (int p = 0; p < 4; p++) {
    					int nx = i + dx[p], ny = j + dy[p];
    					if (range(nx, ny) && map[nx][ny] == 0) //번식할 수 있는 곳에 너무 넣어줌
    						tmp[nx][ny] += (map[i][j] / cnt); //여러 곳에서 같은 빈칸에 나무를 넣을 수 있기 때문에 += 사용
    				}
    			}
    		}
    	}
    	copy (map, tmp);
    }
    
    public static void select() { //제초제 좌표 정하는 함수
    	tmp = new int[n][n];
    	
    	int mx = -1;//0으로 하면 나무 없는 경우 측정 불가
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			if (map[i][j] > 0) { //나무인 경우
    				int cnt = map[i][j];
    				for (int p = 4; p < 8; p++) { //대각선 4방
    					for (int q = 1; q <= k; q++) { //범위 k만큼
    						int nx = i + dx[p] * q, ny = j + dy[p] * q;
    						if (range(nx, ny)) {
    							if (map[nx][ny] > 0) //나무인 경우에만
    								cnt += map[nx][ny]; //나무 카운트
    							else 
    								break; //그 외 장애물(벽, 제초제 뿌려져 있는 경우, 빈칸)의 경우에는 계산 안하고 바로 그 방향으로 탐색 중단
    						}
    					}
    				}
    				tmp[i][j] = cnt; //tmp 배열에 각 칸의 나무일 때 그 자리에 제초제 뿌렸을 때 박멸할 수 있는 나무를 적어준다
    				mx = Math.max(mx, cnt); //그 중 최댓값 저장
    			}
    		}
    	}

    	List<Point> list = new ArrayList<>();
    	
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < n; j++)
    			if (tmp[i][j] == mx) //최댓값이 여러 개인 경우
    				list.add(new Point(i, j)); // 그 좌표들을 전부 저장
    	
    	if (list.isEmpty()) {//죽일 것이 없는 경우
    		choice = new Point(-1, -1);
    		return;
    	}
    	
    	Collections.sort(list); //그 좌표의 우선순위를 위해 정렬
    	choice = new Point(list.get(0).x, list.get(0).y); //제초제를 뿌렸을 때 가장 많이 박멸되는 칸의 좌표
    }
    
    public static void killing() { //선택된 좌표로 제초제를 뿌리는 함수
    	int x = choice.x, y = choice.y; //좌표
    	
    	copy(tmp, map);
    	
    	//좌표값 처리
    	ans += tmp[x][y]; //박멸할 나무에 더하고
	    tmp[x][y] = -2; //제초제 뿌렸다는 표시
	    kill[x][y] = c; //연(year) 수 저장
    	
		for (int p = 4; p < 8; p++) { //대각선 4방
			for (int q = 1; q <= k; q++) { //확장 범위 k~
				int nx = x + dx[p] * q, ny = y + dy[p] * q;
				if (range(nx, ny)) {
					if (map[nx][ny] >= 0) {//나무가 0~개인 경우
						ans += map[nx][ny];
						tmp[nx][ny] = -2;
						kill[nx][ny] = c;
						if (map[nx][ny] == 0) //0인 경우(아예 없는 경우)는 제초제는 뿌리돼 멈춰야 함
							break;
					}
					else {
						if (map[nx][ny] == -2) //제초제가 이미 뿌려져있는 경우
							kill[nx][ny] = c; //값은 바뀌지만
						break; //더 확장되지는 않음
					}
				}
			}
		}
			
		copy(map, tmp);
    }
    
    public static void copy(int[][] a, int[][] b) {
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < n; j++)
    			a[i][j] = b[i][j];
    }
    
    public static boolean range(int nx, int ny) {
    	if (nx >= 0 && nx < n && ny >=0 && ny < n)
    		return true;
    	return false;
    }
    
    static class Point implements Comparable<Point>{
    	int x, y;
    	
    	public Point(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}

		@Override
		public int compareTo(Point o) {// 문제조건인 "만약 박멸시키는 나무의 수가 동일한 칸이 있는 경우에는 행이 작은 순서대로, 만약 행이 같은 경우에는 열이 작은 칸에 제초제를 뿌리게 됩니다." 구현
			if (o.x == x)
				return y - o.y;
			return x - o.x;
		}
    }
}

 

코드가 너무 길어 모든 걸 설명할 수는 없고 최대한 친절하고 많은 주석을 달았다!!

 

 

 

+

 

맞기까지 걸린 시간

 

예전에 비록 틀렸지만 풀었던 적이 있고, 진짜 거의 안 쉬고 문제 시나리오 짜고 처음으로 돌리고 소소한 에러 고치고 주어진 테케를 다 맞았던 시간이 1시간 58분 정도였다. 그리고 저 위의 6,7번 테케를 맞추고 다 맞은 후의 시간이다. 두 문제 중 쉬운 문제인데도 3시간 걸리네... ㅠㅠ