SWEA 5653 줄기세포 배양

 

풀이방식

Priority Queue를 활용한 시뮬레이션

 

baby : 비활성화 세포 (활성화 시간 기준 PQ)

adult : 번식할 세포 (생명력 기준 PQ)

old : 활성화됐지만 번식하지 않는 세포 (죽는 시간 기준 PQ)

 

활성화되는 시간 : 태어난 시간(birth) + 생명력(power)

죽는 시간 : 태어난 시간(birth) + (생명력(power) * 2)

 

1. 번식

adult 큐에서 상하좌우 탐색

   - 비어있으면 채우기

   - adult에 넣기 

2. 활성

baby 큐에서 (활성화시간 == 현시간)인 애들를 adult에 옮기기

(우선순위 큐이므로 안 되는 애가 나오면 바로 break : 그 뒤로는 이후에 활성화되는 애들이기 때문)

3. 죽은 세포 처리 :

old 큐에서 (죽는 시간==현시간)인 애들을 pop하기

 

소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_5653_줄기세포배양_서울_06_신유진 {
	static class Cell {
		int birth, power, x, y;
		int mature, death;
		public Cell(int birth, int power, int x, int y) {
			super();
			this.birth = birth;
			this.power = power;
			this.x = x;
			this.y = y;
			this.mature = birth+power;
			this.death = birth+(power*2);
		}
		@Override
		public String toString() {
			return "Cell [birth=" + birth + ", power=" + power + ", x=" + x + ", y=" + y + ", mature=" + mature
					+ ", death=" + death + "]";
		}
	}

	static final int dx[] = { -1, 0, 1, 0 };
	static final int dy[] = { 0, 1, 0, -1 };
	static final int delta = 350;
	
	static int h, w, k;
	static int[][] map;
	static Queue<Cell> baby;
	static Queue<Cell> adult;
	static Queue<Cell> old;
	static void init() {
		map = new int[700][700];
		baby = new PriorityQueue<Cell>(new Comparator<Cell>() {

			@Override
			public int compare(Cell o1, Cell o2) {
				if(o1.mature < o2.mature) return -1;
				if(o1.mature > o2.mature) return 1;
				return 0;
			}
			
		});
		adult = new PriorityQueue<Cell>(new Comparator<Cell>() {

			@Override
			public int compare(Cell o1, Cell o2) {
				if(o1.power>o2.power) return -1;
				else if(o1.power<o2.power) return 1;
				return 0;
			}
			
		});
		old = new PriorityQueue<Cell>(new Comparator<Cell>() {
			@Override
			public int compare(Cell o1, Cell o2) {
				if(o1.death<o2.death) return -1;
				else if(o1.death>o2.death) return 1;
				return 0;
			}
			
		});
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		init();
		
		
		System.setIn(new FileInputStream("sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			h = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			init();
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < w; j++) {
					map[delta + i][delta + j] = Integer.parseInt(st.nextToken());
					if (map[delta + i][delta + j] != 0) {
						baby.offer(new Cell(0, map[delta + i][delta + j], delta + i, delta + j));
					}
				}
			}
			
			
			for (int time = 0; time <= k; time++) {
				// 번식
				while(!adult.isEmpty()) {
					Cell now = adult.poll();
					int x = now.x; int y = now.y; int power = now.power;
					for(int i=0; i<4; i++) {
						int nx = x+dx[i]; int ny = y+dy[i];
						if(map[nx][ny]==0) {
							map[nx][ny] = power;
							baby.offer(new Cell(time, power, nx, ny));
						}
					}
					old.offer(now);
				}
				// 활성 
				while(!baby.isEmpty()) {
					Cell now = baby.peek();
					if(now.birth+now.power!=time) break;
					else {
						baby.poll();
						adult.offer(now);
					}
					
				}
				// 죽이기
				while(!old.isEmpty()) {
					Cell now = old.peek();
					if(now.birth+now.power*2!=time) break;
					else {
						old.poll();
					}
				}
				System.out.print("");
			}

			System.out.println("#" + tc + " " + (baby.size()+old.size()+adult.size()));
		}
	}
}

 

우선순위 큐

baby = new PriorityQueue<Cell>(new Comparator<Cell>() {
		// 활성시간 기준 오름차 순
		@Override
		public int compare(Cell o1, Cell o2) {
			if(o1.mature < o2.mature) return -1;
			if(o1.mature > o2.mature) return 1; // swap할 기준
			return 0;
		}
			
});