[CodeTree] 나무박멸(삼성 SW 역량테스트 2022 상반기 오후 2번 문제)

문제

https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all?page=4&pageSize=5

 

---

배운 점

- 3개이상의 if 조건 분기 헷갈리지 않기 

- 입력 데이터 항상성 보장할 것

- 객체 관리

---

코드

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

class TreeGroup {
	int x, y;
	int treeNum;
	
	public TreeGroup(int x, int y, int treeNum) {
		this.x = x;
		this.y = y;
		this.treeNum = treeNum;
	}	
}
public class Main {
	static int N, M, K, C, answer;
	static int[][] board;
	static int[][] jecho;
	
	static int[][] dxy = {{-1,0},{1,0},{0,-1},{0,1}};
	static int[][] dxy2 = {{-1,-1},{1,1},{1,-1},{-1,1}};
	static ArrayList<TreeGroup> trees = new ArrayList<>();
	static ArrayList<Integer> spaceCount;
	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());
		
		board = new int[N][N];
		jecho = new int[N][N];
		answer = 0;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				
				if(board[i][j] != 0 && board[i][j] != -1) {
					trees.add(new TreeGroup(i, j, board[i][j]));
				}
			}
		}
		
		simulation();
		
		System.out.println(answer);
		
	}
	
	static void simulation() { // 전체 시뮬레이션
		
		for(int t = 0; t < M; t++) {
			spaceCount = new ArrayList<>();		
			
			growTree(); // 나무 성장
			widenTree(); // 나무 확장
			searchRemoveTree();
		}
	}
	
	static void growTree() { 
		
		// 인접한 네개의 칸에 대해서 나무가 있다면 그만큼 성장 최대 4
		for(int i = 0; i < trees.size(); i++) {
			int spaceCnt = 0;
			int adjTreeCnt = 0;
			for(int d = 0; d < 4; d++) {
				int nx = trees.get(i).x + dxy[d][0];
				int ny = trees.get(i).y + dxy[d][1];
				if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
				if(board[nx][ny] == 0 && jecho[nx][ny] == 0){
					spaceCnt++;
				}
				if(board[nx][ny] > 0) {
					adjTreeCnt++;
				}
			}	
			
			board[trees.get(i).x][trees.get(i).y] += adjTreeCnt;
			trees.get(i).treeNum += adjTreeCnt;
			spaceCount.add(spaceCnt);
		}
	}
	
	static void widenTree() { // 나무 확장
		int[][] tempBoard = new int[N][N];
		
		// 나무 주변 빈칸(나무 없고, 장애물 없고, 제초제 없는)
		// 만일 두 나무에서 한곳에 확장을 동시에 한다면 더해줌
		for(int i = 0; i < trees.size(); i++) {
			
			if(spaceCount.get(i) == 0) continue;
			
			
			TreeGroup tree = trees.get(i);	
			int childTreeNum = tree.treeNum / spaceCount.get(i);  
			
			for(int d = 0; d < 4; d++) {
				int nx = tree.x + dxy[d][0];
				int ny = tree.y + dxy[d][1];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= N ) continue;
				if(jecho[nx][ny] > 0) continue; // 제초제 없는지 체크
				if(board[nx][ny] != 0) continue; // 다른 나무가 없는 곳은 아닌지 체크
				
				tempBoard[nx][ny] += childTreeNum;
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(tempBoard[i][j] != 0) {
					board[i][j] = tempBoard[i][j];
					trees.add(new TreeGroup(i, j, tempBoard[i][j]));
				}
			}
		}
	}
	
	static void discountJecho() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(jecho[i][j] > 0) jecho[i][j] -= 1;
			}
		}
	}
	
	static void searchRemoveTree() { // 대각 방향의 제거할 나무 수를 찾는 메서드
		//제초제가 있는 칸은 C년이후에 사라짐 제초제에 대한 테이블 따로 관리
		// 만약 박멸시키는 나무의 수가 동일한 칸이 있는 경우에는 행이 작은 순서대로, 만약 행이 같은 경우에는 열이 작은 칸에 제초제를 뿌리게 됨
		int maxNum = -1;
		TreeGroup maxNumTree = null;
		for(int i = 0; i < trees.size(); i++) {
			TreeGroup tree = trees.get(i);
			int x = tree.x;
			int y = tree.y;
			
			if(board[x][y] > 0 && jecho[x][y] == 0) {
				
				int cnt = countRemovableTree(x, y);
				if(cnt > maxNum) {
					maxNum = cnt;
					maxNumTree = tree;
				}
				else if(cnt == maxNum) {
					if(maxNumTree.x == tree.x) {
						maxNumTree = maxNumTree.y < tree.y ? maxNumTree : tree;
					}
					else maxNumTree = maxNumTree.x < tree.x ? maxNumTree : tree;
				}
			}
		}
		
		if(maxNumTree != null) removeTree(maxNumTree.x, maxNumTree.y);
	}
	
	static int countRemovableTree(int x, int y) { 
		int cnt = board[x][y];
		
		for(int d = 0; d < 4; d++) {
			int nx = x;
			int ny = y;
			for(int i = 0; i < K; i++) {
				nx += dxy2[d][0];
				ny += dxy2[d][1];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= N ) break;
				if(board[nx][ny] == -1 || board[nx][ny] == 0) break;
				
				cnt += board[nx][ny];
			}
		}
		
		return cnt;
	}
	
	static void removeTree(int x, int y) { 
		discountJecho();
		
		int numOfRemovedTree = board[x][y];
		board[x][y] = 0;
		removeTreeFromTrees(x,y);
		jecho[x][y] = C;
		
		for(int d = 0; d < 4; d++) {
			int nx = x;
			int ny = y;
			for(int i = 0; i < K; i++) {
				nx += dxy2[d][0];
				ny += dxy2[d][1];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= N ) break;
				if(board[nx][ny] == -1 || board[nx][ny] == 0) {
					jecho[nx][ny] = C;
					break;
				}
				
				numOfRemovedTree += board[nx][ny];
				board[nx][ny] = 0;
				jecho[nx][ny] = C;
				removeTreeFromTrees(nx, ny);
			}
		}
		answer += numOfRemovedTree;
	}
	
	static void removeTreeFromTrees(int x, int y) {
		for(int i = 0; i < trees.size(); i++) {
			TreeGroup tree = trees.get(i);
			if(tree.x == x && tree.y == y)trees.remove(i);
		}
	}
}

---

풀이

1. 메서드 정리

메서드 명	역할	비고
main	- 입력데이터 전처리 - turn 별 과정 진행 - simulation 메서드 호출
void simulation()	- simulation 진행  1. GrowTree() 2. WidenTree() 3. SearchRemoveTree()	spaceCount 리스트 초기화 : 매 턴 별로 확장되는 각 TreeGroup 객체에 대한 주변 빈공간 수를 유지시킴
void growTree()	- 인접한 네 개의 칸들에 대해서 TreeGroup이 존재하면 존재하는 나무 수 만큼 나무 수를 확장시킴
void widenTree()	- 문제에서 제시된 조건들을 바탕으로 주변 빈 공간(벽, 제초제 뿌려진 곳 제외)에 나무 그룹 내 나무의 수를 빈공간의 수로 나누어 몫 만큼 확장시킴
void discountJecho()	정수형 2차원 배열 jecho 배열에 대해 기존에 제초제가 뿌려져 있던 영역의 값을 1 감소시킴 : 매 턴별로 1씩 감소
void searchRemoveTree()	한 나무에 뿌렸을 때 두 개의 대각선 방향으로 어떤 나무에 뿌려야 가장 많은 수의 나무들이 박멸되는지 체크하는 메서드
int countRemovableTree(int x, int y)	나무가 위치한 좌표에 제초제를 살포하면 몇 그루의 나무가 박멸되는지 수를 리턴하는 메서드
void removeTree(int x, int y)	실제 나무를 박멸하는 메서드
void removeTreeFromTrees(int x, int y)	나무 그룹에서 나무를 제거하는 메서드(Trees 리스트에서 TreeGroup 객체를 제거) by 좌표비교

 

- 해당 문제는 정말 시뮬레이션 문제였다. 문제에서 주어진 조건을 바탕으로 if 분기 처리 및 객체 관리의 조합으로 푸는 문제여서 별도의 알고리즘 개념이 필요하진 않았다. 

- 그래프 탐색을 넣으려고 하면 넣을 순 있겠지만 그냥 dxy(상하좌우), dxy2(좌상->우하, 우상->좌하 대각선 방향) 배열을 선언해놓고 반복문을 돌리는 방식으로 구현하였다.