[모의 SW 역량테스트] 줄기세포배양 -Java

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE

SW Expert Academy

package SW_Expert_Academy;

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

public class 줄기세포배양 {
	static class Cell{
		int x,y,hp,active,dead;
		public Cell(int x, int y, int hp, int active, int dead) {
			this.x = x;
			this.y = y;
			this.hp = hp;
			this.active = active;
			this.dead = dead;
		}
	}
	static int []dx= {0,0,-1,1};
	static int []dy= {-1,1,0,0};
	static int map[][],N,M,K;
	static List <Cell> cellList;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T=Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			cellList = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			M=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			map = new int[N+(2*K)+1][M+(2*K)+1];
			
			for(int i=0; i<N; i++) {
				 st = new StringTokenizer(br.readLine());
				for(int j=0; j<M; j++) {
					map[i+K][j+K]=Integer.parseInt(st.nextToken());
					if(map[i+K][j+K]!=0) cellList.add(new Cell(i+K, j+K, map[i+K][j+K], 0,0));
				}
			}
			System.out.println("#"+tc+" "+solve());
		}
		
	}
	
	private static int solve() {
		int time=0;
		
		while(true) {
			time++;
			cellBfs();
			cellDead();
			if(time==K) return cellList.size();
		}
		
	}

	private static void cellDead() {
		int size=cellList.size();
		for(int i=size-1; i>=0 ; i--) {
			Cell cell=cellList.get(i);
			if(cell.dead==0 && cell.active==cell.hp) cellList.remove(i);
		}
		
	}

	private static void cellBfs() {
		
		 List <Cell> newCellList = new ArrayList<>();
		PriorityQueue<Cell> pq = new PriorityQueue<>((o1,o2)->(o2.hp-o1.hp));
		//활성상태 (active==hp) 이고 안죽은거 dead!=0
		for(Cell cell : cellList) {
			if(cell.active==cell.hp && cell.dead!=0) {
				cell.dead--;
				pq.offer(new Cell(cell.x,cell.y,cell.hp,cell.active,cell.dead));
			}
		}
		
		while(!pq.isEmpty()) {
			Cell cell= pq.poll();
			
			for(int i=0; i<4; i++) {
				int nx=cell.x+dx[i];
				int ny=cell.y+dy[i];
				
				if(map[nx][ny]!=0) continue;
				
				map[nx][ny]=cell.hp;
				newCellList.add(new Cell(nx,ny,cell.hp,0,0));
			}
		}
		
		activePlus(); //이전에 존재하는 cell active++해주기
		
		for(Cell cell : newCellList) {
			cellList.add(new Cell(cell.x,cell.y,cell.hp,cell.active,cell.dead));
		}
	}

	private static void activePlus() {
		for(Cell cell : cellList) {
			if(cell.active==cell.hp) continue;
			if(++cell.active==cell.hp) cell.dead=cell.hp;
		}
	}
}

 

소요시간 : 1시간

 

전형적인 시뮬레이션 문제입니다. 그냥 문제에서 구현하라는 방식으로 잘 구현하면 됩니다..

 

우선 map크기는 map = new int[N+(2*K)][M+(2*K)] 로 만들었습니다.

왜 N+(2*K), M+(2*K)로 만들었냐면

일단 가로세로 크기가 N,M으로 들어오는데 여기서 아무리 커져봤자 K번만큼만 커지게 됩니다.

근데 좌로 계속 커질수도있고, 우로 계속 커질 수도 있고, 위아래도 마찬가지이기 때문에 2K를 주는 것입니다!

 

이렇게 map을 만들었다면 사실상 문제를 다 풀었다고도 볼 수 있습니다.

 

그 후 로직은

 

1.활성상태인 세포를 상대로 BFS를 돌린다. (이때 생성되는 세포들은 newCellList라는 곳에 저장해둔다)

2. 원래 저장돼있던, 즉 cellList의 세포들의 active를 1씩 늘려준다 ( active 가 hp와 같아지면 활성 상태)

3.new CellList와 cellList를 합친다.

4. 죽은 세포를 cellList에서 삭제해준다.

 

입니다.

 

세포가 죽었는지, 살았는지, 활성인지, 비활성인지만 변수로 잘 체크한다면 쉬운 문제라고 생각합니다!