코드 트리 - 나무 박멸(46번)

❓ 문제 - 코드 트리(code tree) 나무 박멸 46번 - JAVA 풀이법

 

출처

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

코드트리

 

 

 

📝 문제해결법

1. 문제

• 나무의 성장 -> 나무의 번식 -> 최대 많은 나무를 죽일 제초제 뿌릴 위치 선정 -> 제초제 뿌림의 단계로 m년 진행했을 때 제초제로 죽인 나무의 수를 구하는 문제이다.

 

2. 해결 방법

• 문제 구현 부분을 크게 나무의 성장 -> 나무의 번식 -> 최대 많은 나무를 죽일 제초제 뿌릴 위치 선정 -> 제초제 뿌림의 단계로 나눈다.
  • 나무의 성장은 grow() 함수, 나무의 번식은 moving() 함수, 제초제 위치 선정은 pick()함수, 제초제 뿌린 후 나무 죽이는 것은 main for문 안에서 처리한다.
• grow() - 나무의 성장
  • map에 저장된 값을 기준으로 i, j행의 4방향으로 나무가 존재하는 것을 count한 후 그 값을 i, j에 더해준다.
• moving() - 나무의 번식
  • 나무의 번식은 동시에 일으나므로 map2라는 2차원 배열을 하나 더 선언해서 번식된 나무의 값을 map2에 저장하고 map1에 더해줌으로써 처리한다.
  • 나무가 있는 곳을 기준으로 4방향(상, 하, 좌, 우)를 탐색하면서 칸이 빈 곳을 count 해주고, 그 값을 기준으로 현재 나무의 갯수 / count 된 수를 4방향(상, 하, 좌, 우)로 더해준다.
  • 이 때, 번식을 처리할 때 문제에서 주어진 경우로 빈 영역이고, 만약 제초자가 뿌려져 있다면 동시에 제초제를 뿌린 시점과 현재 시점의 기준 차이가 c 이상일 때만 번식할 수 있도록 구현했다.
  • 마지막에 동시 처리를 위해 map2에 번식된 나무 수를 다시 map1에 더해준다.
• pick()  -제초제 위치 선정
  • 일단 ArrayList에 Node로 현재까지 구한 최대 나무를 죽일 수 있는 Node를 리스트에 넣어주는데, list를 만약 정렬한다면 죽일 수 있는 나무 수(최대), 그리고 나무 수가 같다면 행을 기준(최소)으로, 그 다음은 행이 같다면  열(최소)을 기준으로 정렬할 수 있도록 구현한다.
  • 2차원 배열로 map을 돌면서 대각선으로 k배의 길이만큼, 죽일 수 있는 나무 수를 카운트해서 최대 죽일 수 있는 나무 수를 구한다.
  • 이때, 제초제를 뿌릴 때 만약 탐색한 곳이 벽이거나 나무가 없는 곳이면 해당 영역까지만 탐색하고 그 이상은 탐색하지 않도록 하는 것이 구현 포인트이다.
• 제초제 죽임 처리
  • die 2차원 배열에 최적의 제초제를 뿌린 위치를 기준으로 다시 대각선을 k의 거리만큼 제초제를 뿌리고 나무를 죽임처리(map의 값을 0으로) 해준다.
  • 이때, 제초제 위치 선정과 동일하게  벽이거나 나무가 없는 곳이라면 거기까지만 제초제를 뿌리고, 그 이상의 영역에서는 탐색을 멈추도록 구현하는 것이 포인트이다.

 

3. 느낀점

• 2번째 케이스에서 자꾸 이상해서 출력 디버깅했더니 바로 해결했다.
• 그리고 코드트리에서 돌려봤는데 7번 케이스에서.. 자꾸 틀리길래 ㅠ 문제를 다시 정확하게 읽어보면서 주어진 조건과 내 구현이 다른 점이 있는지 파악했고 바로 제초제를 뿌릴 때 나무가 없는 영역 이상의 곳은 더이상 뿌리지 않도록 하는 것을 빼먹었다. 이것을 바로 잡고 돌리니 통과!
• 오랜만에 알고리즘을 풀어서 약간 감이 없는데 이렇게, 테케가 안 통과하면 문제를 다시 천천히 읽어보면서 문제에서 글자 하나라도 조건 뽑아서 구현이 적용되었는지 파악하는 습관은 좋은 것 같다.

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;


public class Solution_46 {
	public static int n, m, k, c;
	public static int[][] map;
	public static int[][] die;
	public static class Node implements Comparable<Node>{
		int x;
		int y;
		int cnt;
		public Node(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
		@Override
		public int compareTo(Node o) {
			if(this.cnt == o.cnt) {
				if(this.x == o.x) {
					return this.y - o.y;
				}
				return this.x - o.x;
			}
			return o.cnt - this.cnt;
		}
	}
	public static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
	public static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
	
	public static void main(String[] args) throws Exception {
		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());
		map = new int[n][n];
		die = new int[n][n];
		long cnt = 0;
		
		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());
			}
		}
		
		for(int p=1;p<=m;p++) {
			// 나무의 성장
			grow();
			// 나무의 번식
			moving(p);
			

			// 제초제 위치 선정
			Node node = pick();
			cnt += node.cnt;
			
			// 제초제 뿌리기
			for(int d=4;d<8;d++) {
				for(int s=0;s<=k;s++) {
					int nx = node.x + dx[d]*s;
					int ny = node.y + dy[d]*s;
					if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					die[nx][ny] = p;
					if(map[nx][ny] > 0) {
						if(nx == node.x && ny == node.y) continue; 
						map[nx][ny] = 0;
					} else {
						break;
					}
					
				}
			}
			map[node.x][node.y] = 0;


		}
		
		System.out.println(cnt);
	}
	
	public static Node pick() {
		ArrayList<Node> list = new ArrayList<>();
		int max = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j] == -1) continue;
				int count = 0;
					
				for(int d=4;d<8;d++) {
					for(int s=0;s<=k;s++){
						int nx = i + dx[d]*s;
						int ny = j + dy[d]*s;
						if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if(map[nx][ny] > 0) { 
							count += map[nx][ny];
						} else {
							break;
						}
						
					}
				}
				count -= map[i][j]*3;

				if(count > max) {
					max = count;
					list.clear();
					list.add(new Node(i, j, count));
				} else if(count == max) {
					list.add(new Node(i, j, count));
				}
			}
		}
		
		if(list.size() != 0) Collections.sort(list);
		return list.get(0);
	}
	
	public static void moving(int p) {
		int[][] map2 = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[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(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if(map[nx][ny] == 0 && (die[nx][ny] == 0 || p - die[nx][ny] > c)) count++;
				}
				
				for(int d=0;d<4;d++) {
					int nx = i + dx[d];
					int ny = j + dy[d];
					if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if(map[nx][ny] == 0 && (die[nx][ny] == 0 || p - die[nx][ny] > c)) {
						map2[nx][ny] += (map[i][j] / count);
					}
				}
				
			}
		}

		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				map[i][j] += map2[i][j];
			}
		}
	}
	
	public static void grow() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[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(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if(map[nx][ny] > 0) count++;
				}
				map[i][j] += count;
			}
		}
		
	}

}