(JAVA) 5653. [모의 SW 역량테스트] 줄기세포배양

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWXRJ8EKe48DFAUo

시간 별로 처리하는 로직을 잘 짜면 되는 문제.
– K시간 동안 M*N 크기의 맵에 있는 세포가 증식하는거라서 (K+M+K)*(K+N+K) 크기의 map 배열을 만듦 (최대값)
– 각 cell 별로 상태 (0: 비활성화/1: 활성화/2: 죽음) 배열, 지정 시간 (증식할 때 사용) 배열, 남은 시간 (상태 변경 때 사용) 배열을 만듦
– 매 시간 마다,
* 비활성화 상태에서는 시간을 1씩 줄이고 0이 되면 활성화 상태로 넘어감 (status 0 > 1)
* 활성화 상태에서는 좌/우/상/하 순으로 주변 셀이 비어있는지 확인하고 비어있으면 증식, 비어있지 않은데 현재 시간에 증식한 경우에는 더 큰 세포 값으로 치환, 이외의 경우에는 무시.
이후 시간을 1씩 줄이고 0이 되면 죽음 상태로 넘어감 (status 1>2)
(status 0>1에서는 시간이 >0인 상태로 넘어오고, status 1>2에서는 시간이 0이 되면 status 2로 넘어가기 때문에 문제 없음)
– k 시간이 흐른 후, 상태가 0 혹은 1인 경우의 갯수를 카운트해서 결정

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

public class Solution {
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // map 세로 길이 (Y)
				int numM = Integer.parseInt(tmp[1]); // map 가로 길이 (X)
				int numK = Integer.parseInt(tmp[2]); // 배양 시간								
				int numCell = 0;
				
				// 최대 공간을 계산
				int[][] map = new int[numM + 2 * numK][numN + 2 * numK];

				int[] cellX = new int[(numM + 2 * numK)*(numN + 2 * numK)];
				int[] cellY = new int[(numM + 2 * numK)*(numN + 2 * numK)];
				int[] cellStatus = new int[(numM + 2 * numK)*(numN + 2 * numK)];	// 0: 비활성화, 1: 활성화, 2: 죽음
				int[] cellTime = new int[(numM + 2 * numK)*(numN + 2 * numK)];		// 지정 시간
				int[] cellRemainingTime = new int[(numM + 2 * numK)*(numN + 2 * numK)];		// 남은 시간
				
				for (int i = 0; i < numN; i++) { // 세로 길이
					tmp = reader.readLine().split(" ");
					for (int j = 0; j < tmp.length; j++) { // numM (가로 길이)
						int value = Integer.parseInt(tmp[j]);
						
						if (value != 0) { // 세포가 존재
							cellX[numCell] = numK + j;
							cellY[numCell] = numK + i;
							cellTime[numCell] = value;
							cellRemainingTime[numCell] = value;
							
							map[numK + j][numK + i] = value; // map에 값 넣음
							
							numCell++;
						}
					}
				}
				
				// 실제 배양 시도 (1 ~ numK 시간) (i=0일 때 1시간 후의 결과가 나옴)
				for (int i = 0; i < numK; i++) {
					// 이번에 증식된 세포 리스트 (이미 있는 세포와 구분)
					List<String> currentAddedCell = new ArrayList<String>();
					
					int currNumCell = numCell;
					for (int j = 0; j < currNumCell; j++) {
						switch (cellStatus[j]) {
						case 0: // 비활성화
							cellRemainingTime[j]--;
							
							if (cellRemainingTime[j] == 0) {
								cellStatus[j] = 1; // 정해진 시간이 지나면 활성화
								cellRemainingTime[j] = cellTime[j];
							}
								
							break;
						case 1: // 활성화
							int currentX = cellX[j];
							int currentY = cellY[j];
							
							// 좌 증식
							if (map[currentX - 1][currentY] == 0) { // 비어 있는 경우
								map[currentX - 1][currentY] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX - 1) + "/" + String.valueOf(currentY));
								
								cellX[numCell] = currentX - 1;
								cellY[numCell] = currentY;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX - 1) + "/" + String.valueOf(currentY)) == true) {
									if (map[currentX][currentY] > map[currentX - 1][currentY]) {
										map[currentX - 1][currentY] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX - 1 && cellY[k] == currentY) {
												cellRemainingTime[k] = map[currentX - 1][currentY];
												break;
											}
										}
									}
								}
							}
							// 우 증식
							if (map[currentX + 1][currentY] == 0) { // 비어 있는 경우
								map[currentX + 1][currentY] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX + 1) + "/" + String.valueOf(currentY));
								
								cellX[numCell] = currentX + 1;
								cellY[numCell] = currentY;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX + 1) + "/" + String.valueOf(currentY)) == true) {
									if (map[currentX][currentY] > map[currentX + 1][currentY]) {
										map[currentX + 1][currentY] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX + 1 && cellY[k] == currentY) {
												cellRemainingTime[k] = map[currentX + 1][currentY];
												break;
											}
										}
									}
								}
							}
							// 상 증식
							if (map[currentX][currentY - 1] == 0) { // 비어 있는 경우
								map[currentX][currentY - 1] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX) + "/" + String.valueOf(currentY - 1));
								
								cellX[numCell] = currentX;
								cellY[numCell] = currentY - 1;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX) + "/" + String.valueOf(currentY - 1)) == true) {
									if (map[currentX][currentY] > map[currentX][currentY - 1]) {
										map[currentX][currentY - 1] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX && cellY[k] == currentY - 1) {
												cellRemainingTime[k] = map[currentX][currentY - 1];
												break;
											}
										}
									}
								}
							}
							// 하 증식
							if (map[currentX][currentY + 1] == 0) { // 비어 있는 경우
								map[currentX][currentY + 1] = cellTime[j];
								// 이번에 추가함 (더 큰 수치의 배양 세포 나오면 덮어씌우기) 
								currentAddedCell.add(String.valueOf(currentX) + "/" + String.valueOf(currentY + 1));
								
								cellX[numCell] = currentX;
								cellY[numCell] = currentY + 1;
								cellRemainingTime[numCell] = cellTime[j];
								cellTime[numCell] = cellTime[j];

								numCell++;
							}
							else { // 이미 있는 경우
								// 이번에 추가한 경우 덮어씌울 수 있으면 덮어씌움
								if (currentAddedCell.contains(String.valueOf(currentX) + "/" + String.valueOf(currentY + 1)) == true) {
									if (map[currentX][currentY] > map[currentX][currentY + 1]) {
										map[currentX][currentY + 1] = map[currentX][currentY]; // 최대값 갱신
										for (int k = currNumCell; k < numCell; i++) { // 남은 시간 갱신
											if (cellX[k] == currentX && cellY[k] == currentY + 1) {
												cellRemainingTime[k] = map[currentX][currentY + 1];
												break;
											}
										}
									}
								}
							}
							
							// 남은 시간 줄임
							cellRemainingTime[j]--;
							
							if (cellRemainingTime[j] == 0) {
								cellStatus[j] = 2; // 정해진 시간이 지나면 죽음
							}
							break;
						//case 2: // 죽음 
						//	break;
						}
					}
				}
				
				int answer = 0;
				for (int i = 0; i < numCell; i++) {
					if (cellStatus[i] != 2)
						answer++;
				}
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.