[SWEA] 5653. 줄기세포배양 (구현/Java)

[SWEA] 5653. 줄기세포배양

 

📌 문제 과정

◾ 문제 조건

1. 세포는 생명력 수치에 따라 일정 시간이 지나면 활성화되고, 그 후 상하좌우로 번식한다.
2. 두 개 이상의 세포가 같은 위치로 번식하려고 하면 생명력이 높은 세포만 번식에 성공한다.
3. 시간 경과에 따라 세포는 비활성화 → 활성화 → 죽음의 과정을 거친다.

생명력 수치가 X인 줄기 세포의 경우
X시간 동안 비활성 상태이고 X시간이 지나는 순간 활성 상태가 된다.
줄기 세포가 활성 상태가 되면 X시간 동안 살아있을 수 있으며 X시간이 지나면 세포는 죽게 된다.

이 조건을 제대로 안봐서 조큼 삽질한...

 

◾ 맵 크기 초기화

세포가 K 시간 동안 번식하며 범위가 확장되기 때문에

배양 시간에 따라 충분한 공간을 확보하기 위해 맵의 크기를 N + 2 * K 로 설정한다.

 

◾ 두개의 큐 사용하기

PriorityQueue<Cell> pq

세포의 번식 순서를 관리한다. 세포의 생명력이 클수록 우선적으로 처리되도록 했기 때문에

두 개 이상의 세포가 같은 위치로 번식하려고 할 때의 경우는 고려하지 않아도 된다.

pq = new PriorityQueue<>((c1, c2) -> {return c2.life - c1.life;});

Queue<Cell> q

현재 턴(시간)에서 번식이 끝난 세포들과 활성 상태가 유지되는 세포를 임시로 저장하고

한 턴이 끝난 후 다시 pq에 넣어 다음 번식에서 처리되도록 한다.

 

◾ 세포가 번식하는 과정

life : 세포의 생명력

time : 세포가 활성화되기까지 남은 시간과 생명력을 관리한다.

1. 세포가 활성화된 순간부터 상하좌우 네 방향으로 번식을 시작한다.
2. 번식할 때, 세포가 번식하려는 위치가 이미 다른 세포에 의해 차지되지 않은 경우에만 번식 가능하다.
3. 세포는 활성화된 후 X 시간 동안 번식하며, 그 이후에는 죽는다. 죽은 세포는 더 이상 번식하지 않으며, 큐에 추가하지 않는다.

세포가 죽은 경우 q에 추가하지 않기 때문에 pq를 통해서 최종적으로 남아있는 세포만 카운트 할 수 있다.

private static void bfs() {
	Queue<Cell> q = new LinkedList<>();
		
	while (K-- > 0) {
		while (!pq.isEmpty()) {
        	Cell cell = pq.poll();
                ...
			if(cell.life + cell.time == 0) continue;
			q.offer(cell);
		}			
        
		while(!q.isEmpty()) pq.offer(q.poll());
	}
}

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class 줄기세포배양_5653 {

	static int N, M, K;
	static int[][] d = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static boolean[][] visited;
	static PriorityQueue<Cell> pq;

	static class Cell {
		int x, y, life, time;

		Cell(int x, int y, int life, int time) {
			this.x = x;
			this.y = y;
			this.life = life;
			this.time = time;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 세로 크기
			M = Integer.parseInt(st.nextToken()); // 가로 크기
			K = Integer.parseInt(st.nextToken()); // 배양 시간
			visited = new boolean[N + 2 * K][M + 2 * K]; // 크기 확보

			pq = new PriorityQueue<>((c1, c2) -> {
				return c2.life - c1.life;
			});

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					int life = Integer.parseInt(st.nextToken());
					if (life > 0) {
						visited[i + K][j + K] = true;
						pq.add(new Cell(i + K, j + K, life, life)); // 초기 세포 추가
					}
				}
			}

			bfs();
			
			sb.append("#" + t + " " + pq.size() + "\n");
		}
		
		System.out.println(sb.toString());
	}

	private static void bfs() {
		Queue<Cell> q = new LinkedList<>();
		
		while (K-- > 0) {
			while (!pq.isEmpty()) {
				Cell cell = pq.poll();
				cell.time--;

				if (cell.time < 0) {
					for (int i = 0; i < 4; i++) {
						int nx = cell.x + d[i][0];
						int ny = cell.y + d[i][1];

						if(visited[nx][ny]) continue;
						
						visited[nx][ny] = true;
						q.offer(new Cell(nx, ny, cell.life, cell.life));
					}
				}
				
				if(cell.life + cell.time == 0) continue;
				q.offer(cell);
			}
			
			while(!q.isEmpty()) pq.offer(q.poll());
		}

	}
}