알고리즘/SWEA
SWEA 모의 5653 줄기세포 배양
- -
반응형
SWEA 모의 5653 줄기세포 배양
문제링크
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.
동영상 설명
1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.
소스 보기
동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.
더보기
package se.code.모의;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* @author itsmeyjc
* @since 2020. 2. 23.
* @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE
* @mem 96,892 kb
* @time 433 ms
* @caution #simulation
* 무한대로 표시되어있지만 배양 시간 K에 좌우 되기 때문에 세로는 최대 R+K+2, 가로는 최대 C+K+2 (R, C, K 모두 1부터 시작한다.)의 크기를 갖고
* 초기 위치는 r+K/2, c+K/2이다.
*/
public class SWEA_모의_5653_줄기세포배양 {
static StringBuilder sb = new StringBuilder();
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 세포의 상태
static int ABLED = 1, DEAD = -1, DISABLED = 0;
static int TC, R, C, K;
static boolean[][] map;
static PriorityQueue<Cell> liveCells;// 살아있는 세포들(활성화 + 비활성화)
static Queue<Cell> newCells = new LinkedList<>();// 새롭게 추가되는 세포들
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br = new BufferedReader(new StringReader(src));
TC = Integer.parseInt(br.readLine());
for (int t = 1; t <= TC; t++) {
// type solution for tc here
StringTokenizer tokens = new StringTokenizer(br.readLine());
R = Integer.parseInt(tokens.nextToken());// 세로 크기 1≤N≤50
C = Integer.parseInt(tokens.nextToken());// 가로 크기 1≤M≤50
K = Integer.parseInt(tokens.nextToken());// 배양 시간 1≤K≤300
map = new boolean[R + K + 2][C + K + 2];
liveCells = new PriorityQueue<>();
for (int r = 0; r < R; r++) {
tokens = new StringTokenizer(br.readLine());
for (int c = 0; c < C; c++) {
int life = Integer.parseInt(tokens.nextToken());
if (life > 0) {
Cell cell = new Cell(r + K / 2, c + K / 2, life);
map[cell.r][cell.c] = true;
liveCells.offer(cell);
}
}
}
// System.out.println("입력 완료: " + liveCells);
// 입력 완료
for (int k = 0; k < K; k++) {
// 새롭게 추가되는 셀들을 관리
newCells.clear();
while (!liveCells.isEmpty()) {
Cell cell = liveCells.poll();
// 비활성화의 경우 - 활성화 여부 파악 후 다시 관리 필요
if (cell.status == DISABLED) {
cell.wait--;
if (cell.wait == 0) {
cell.status = ABLED;
}
newCells.offer(cell);
}
// 활성화된 경우 사방으로 번식한다.
else if (cell.status == ABLED) {
for (int d = 0; d < dirs.length; d++) {
int nr = cell.r + dirs[d][0];
int nc = cell.c + dirs[d][1];
// 선점 세포가 없다면 추가해준다. 만약 기존 세포가 있다면 원래 부터 있었거나 동일한 턴이었다면 더 쎈놈이다.
if (!map[nr][nc]) {
map[nr][nc] = true;
newCells.add(new Cell(nr, nc, cell.life));
}
}
// ABLED 상태에서는 life가 하나씩 줄고 0보다 크면 계속 관리
cell.life--;
if (cell.life > 0) {
newCells.offer(cell);
}
}
} // 모든 셀들에 대한 동작이 종료 - 동시에 하는 작업이 완료
// 전체 관리 대상에 모조리 추가
while (!newCells.isEmpty()) {
liveCells.offer(newCells.poll());
}
} // k 반복 종료
sb.append("#").append(t).append(" ").append(liveCells.size()).append("\n");
////////////////////////////
}
System.out.println(sb);
}
// 강한놈이 살아 남기 때문에 life가 높은 녀석부터 사용하기 위해 정렬 처리
static class Cell implements Comparable<Cell> {
int r, c;// row, col,
int wait;// 활성화까지 남은 시간,
int life; // 살아있는 시간,
int status;// status: -1: 사망, 0: 비활성(default), 1: 활성
public Cell(int r, int c, int life) {
this.r = r;
this.c = c;
this.wait = this.life = life;
}
@Override
public String toString() {
return "[(" + r + ", " + c + "), l=" + wait + "," + life + ", s=" + status + "]";
}
@Override
// life에 대한 내림차순
public int compareTo(Cell o) {
return Integer.compare(o.life, life);
}
}
private static String src = "5\r\n" +
"2 2 10\r\n" +
"1 1\r\n" +
"0 2\r\n" +
"5 5 19\r\n" +
"3 2 0 3 0 \r\n" +
"0 3 0 0 0 \r\n" +
"0 0 0 0 0 \r\n" +
"0 0 1 0 0 \r\n" +
"0 0 0 0 2\r\n" +
"9 10 37\r\n" +
"0 0 0 0 0 0 0 0 3 0 \r\n" +
"0 0 0 0 0 0 0 0 5 3 \r\n" +
"0 0 2 0 0 0 0 4 0 0 \r\n" +
"3 0 0 0 0 0 4 0 0 0 \r\n" +
"0 0 0 0 0 3 5 0 0 2 \r\n" +
"0 0 0 0 0 0 0 0 0 5 \r\n" +
"0 0 0 0 0 0 0 0 2 3 \r\n" +
"0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 2 2 0 0 0 0 0 0 \r\n" +
"20 18 83\r\n" +
"0 0 0 0 0 0 0 0 0 0 0 2 0 0 6 0 0 0 \r\n" +
"0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 6 0 0 0 0 0 0 0 0 0 0 2 0 3 0 \r\n" +
"4 0 2 0 0 0 0 0 0 0 0 0 5 0 0 0 0 3 \r\n" +
"0 0 0 0 0 5 4 4 6 0 0 0 0 0 0 0 0 0 \r\n" +
"5 0 0 0 0 0 2 0 2 6 0 0 0 0 0 4 0 0 \r\n" +
"4 0 0 3 0 0 0 0 0 0 0 3 0 0 0 5 0 0 \r\n" +
"0 0 0 0 0 0 0 2 2 0 0 0 0 3 0 0 0 0 \r\n" +
"0 0 0 0 5 0 0 0 3 0 3 0 0 4 0 0 0 0 \r\n" +
"0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 0 6 0 2 0 0 0 0 0 3 0 0 0 3 0 \r\n" +
"0 5 2 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 \r\n" +
"3 0 0 0 0 0 0 0 6 0 2 0 5 0 0 0 0 0 \r\n" +
"5 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 6 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 4 0 0 0 0 0 0 0 0 0 0 2 0 0 0 \r\n" +
"0 0 3 4 5 0 0 0 0 0 0 0 0 0 0 6 0 0 \r\n" +
"2 0 0 0 0 3 0 0 0 0 0 0 0 0 0 5 0 0 \r\n" +
"0 0 0 0 0 0 0 0 0 3 6 2 0 0 0 0 0 0 \r\n" +
"49 43 283\r\n" +
"0 6 0 0 0 10 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 4 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 \r\n" +
"0 5 0 0 0 2 0 0 0 0 0 0 8 0 0 8 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 3 7 0 0 0 0 0 0 9 0 1 0 5 0 0 1 0 0 0 0 0 0 0 0 0 0 0 9 0 7 0 0 0 0 0 0 0 0 1 0 0 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 8 0 0 0 0 0 0 0 0 0 3 0 0 0 6 0 0 0 0 6 0 0 0 0 0 0 \r\n" +
"7 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 8 0 0 0 0 0 0 0 0 1 0 0 \r\n" +
"0 9 0 0 0 0 0 0 0 0 9 6 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 \r\n" +
"0 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 5 0 10 0 0 0 0 0 0 0 0 0 9 4 0 0 0 0 0 0 9 0 9 0 8 \r\n" +
"0 0 0 0 0 0 0 0 0 7 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 0 1 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 \r\n" +
"0 0 0 0 0 0 0 0 0 7 0 0 0 2 0 0 0 0 0 0 8 0 0 0 0 10 0 0 1 7 0 8 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 0 0 0 0 2 0 0 9 0 0 0 0 0 8 0 0 0 0 0 4 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"1 0 0 0 0 0 0 6 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 5 0 0 0 0 0 0 7 0 0 0 \r\n" +
"8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 5 8 \r\n" +
"0 0 0 10 0 9 0 8 0 0 0 0 0 0 2 9 0 0 0 7 2 7 0 7 0 0 0 0 2 0 4 3 0 0 0 0 0 0 0 0 0 2 0 \r\n" +
"1 0 0 0 0 0 0 4 9 1 0 0 0 0 0 0 0 0 0 5 0 0 0 0 6 0 0 5 0 0 0 0 0 0 0 0 0 0 0 3 3 0 0 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 1 0 3 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 1 0 0 0 9 0 0 \r\n" +
"0 0 0 0 0 0 0 10 0 0 0 0 0 0 9 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 1 3 0 0 \r\n" +
"0 0 0 0 0 0 6 0 0 0 1 0 0 2 0 0 0 0 9 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 7 7 0 0 \r\n" +
"0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 5 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 \r\n" +
"0 0 0 0 9 0 8 0 0 0 0 0 0 4 0 0 0 10 8 0 0 0 0 0 0 10 0 0 0 5 0 0 0 0 0 0 0 1 0 0 10 4 7 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 4 0 7 0 0 0 0 0 3 0 \r\n" +
"0 0 0 0 5 0 3 0 0 0 0 0 0 0 8 1 0 0 7 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 9 0 1 0 0 0 0 10 7 0 0 0 0 0 2 0 0 7 0 0 0 0 0 0 0 7 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 0 0 0 0 8 2 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 8 0 0 7 0 2 0 0 0 0 \r\n" +
"0 8 0 0 0 0 0 0 0 0 3 0 0 1 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 5 0 9 0 0 0 0 0 \r\n" +
"0 0 0 0 0 0 0 0 3 5 0 0 1 0 4 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 5 0 0 4 0 0 0 0 10 8 0 0 0 \r\n" +
"0 0 0 0 0 0 0 0 4 0 0 7 10 0 10 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 8 3 9 6 7 0 0 0 0 2 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 8 7 10 0 0 0 0 0 0 6 0 0 0 5 0 0 0 0 0 0 0 0 0 0 10 0 \r\n" +
"7 0 0 0 8 0 0 0 8 9 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 6 0 0 5 0 0 0 0 0 0 0 0 0 0 3 0 0 0 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 6 0 6 0 0 0 0 3 0 0 5 3 0 0 0 0 1 9 0 6 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 7 2 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 8 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 6 \r\n" +
"0 9 0 0 0 0 0 0 0 0 0 3 0 9 2 0 0 0 4 0 2 9 2 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 \r\n" +
"0 0 0 3 0 1 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 7 0 6 0 0 0 0 0 7 0 0 0 0 4 7 10 \r\n" +
"1 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 8 0 0 0 0 0 0 0 0 3 9 2 \r\n" +
"5 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 8 0 0 0 0 0 0 0 3 0 0 0 0 0 \r\n" +
"0 0 0 0 7 0 10 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 8 2 3 0 0 \r\n" +
"0 0 0 0 0 5 0 0 6 0 0 3 0 0 0 0 0 8 0 0 6 0 0 0 8 0 0 5 0 0 0 0 8 0 0 0 0 0 0 0 5 0 1 \r\n" +
"7 0 9 0 7 0 0 9 0 0 0 0 4 0 0 0 0 0 0 8 1 0 4 0 0 0 0 0 0 0 0 0 4 7 0 0 8 0 0 0 0 0 0 \r\n" +
"0 0 0 1 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 2 3 1 0 0 4 0 3 10 0 0 0 5 \r\n" +
"0 0 4 0 0 0 0 0 0 4 4 0 0 0 8 0 4 0 2 0 8 0 0 0 0 0 0 0 9 0 0 0 0 5 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 8 0 7 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 6 0 0 0 0 1 0 0 0 0 4 3 \r\n" +
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 10 3 0 0 0 0 0 3 0 \r\n" +
"0 0 2 0 0 0 0 0 8 5 0 0 0 0 0 0 0 0 0 0 0 0 4 8 0 0 0 0 0 1 0 5 0 0 0 0 2 3 9 0 0 0 0 \r\n" +
"0 5 8 9 0 0 0 0 0 4 0 0 0 10 0 0 0 1 0 0 0 0 0 10 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"6 0 0 0 0 0 10 0 5 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 \r\n" +
"0 0 0 0 0 0 9 0 0 0 0 0 0 2 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 2 4 0 \r\n" +
"0 3 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 \r\n" +
"0 0 0 9 0 0 0 0 4 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 9 2 0 \r\n" +
"0 0 0 0 0 2 0 0 0 0 0 0 10 0 0 0 0 0 2 0 0 0 8 0 0 0 0 0 0 10 0 0 0 0 0 0 7 0 0 0 0 0 0 ";
}
반응형
'알고리즘 > SWEA' 카테고리의 다른 글
| SWEA 모의 1949 등산로 조성 (0) | 2020.05.01 |
|---|---|
| SWEA D5 1798 범준이의 제주도 여행계획 (0) | 2020.04.30 |
| SWEA D4 4366 정식이의 은행업무 (0) | 2020.04.27 |
| SWEA 모의 2117 홈방범서비스 (0) | 2020.04.25 |
| 4796. 의석이의 우뚝 선 산 (0) | 2019.08.08 |
Contents
소중한 공감 감사합니다