줄기 세포 배양

아직 BFS/DFS 완전 탐색 문제를 문제 제시된 조건대로 정확하게 구현해내지 못하는 것 같다. 더 연습해야 할듯..괜찮다 하면 된다!!

복잡한 BFS라고 생각했는데, 줄기 세포 생명력 값과 비활성, 활성 상태 시점에 따른 매커니즘만 이해하면 쉬운 문제인 듯하다.

문제 정리(틀딱박에서 헤어나오기, 우선순위 큐 정렬기준 연습)

주인공은 세포도 아니고, 반복 조건은 시간이 아니다.

중요한 건, 세포의 비활성 시점 값이다.

세포가 번식할 때, 새로 생겨나는 세포의 비활성 시점 값 = 현재 세포의 활성값+1 = 현재 세포의 비활성값(time)+생명력(life)+1

• 비활성 시점 값 기준으로 (생명력X를 더해)활성 시점, 죽는 시점이 결정되고, 비활성 시점 이후에 활성 시점, 죽는 시점이 나오게 된다. (비활성 시간 <활성 시간 < 죽는 시간)

• 배양하는 그리드 크기는 무한대 이기 때문에 무한루프로 구성하되, K 시간 이후의 살아있는 세포 수ans를 구하면 되기 때문에 큐에서 꺼내는 세포마다 죽는 시점이 K보다 크면 1씩 증가 시킨다.

내가 생각했던 풀이방식은?(막혔던 부분)

1. 생성자에 (x,y,age,off,on,alive,die) 위치(x,y), 생명력age, 비활성화시점off, 활성화시점on, 생사여부alive, 사망시점die 총6개의 인자를 전달하는 것이 바람직한지 의문이 들었다.

2. 시간 흐름 순으로 어떻게 배양, BFS 탐색, 사망 처리를 구현하는지 감을 잡을 수가 없었다.

3. 그래도 각 세포마다 비활성 시점(태어난 시점)을 알아야 활성화시점과 사망 시점을 알 수 있기 때문에 비활성화시점을 기록해야한다는 것은 알았다. 활성 시점 = 비활성시점 + 생명력X, 상하좌우로 세포 번식 죽는 시점 = 활성 시점 + 생명력X = 비활성시점 + 2X, 번식한 세포가 비활성화 => 비활성 시점이 기준이다.

정답 솔루션 핵심 비활성 시점 오름차순, 생명력 내림차순 우선순위 큐 세포의 비활성 시점(세포가 발현하는 시점)

자료구조

1. 세포 클래스를 생성 : 위치, 생명력, 비활성 시점을 저장

   static class Cell implements Comparable<Cell> {
           int r, c;// row, col,
           int life; // 살아있는 시간,
           int time;// 턴을 확인하기 위한 값
    
           public Cell(int r, int c, int life, int time) {
               this.r = r;
               this.c = c;
               this.life = life;
               this.time = time;
           }
    
           public int compareTo(Cell o) {
               if (this.time == o.time) {
                   return Integer.compare(o.life, life);
               } else {
                   return Integer.compare(this.time, o.time);
               }
           }
       }

2. 우선순위 큐에 세포 클래스 저장 : 정렬 기준 생성 ① 비활성 시점(태어나는 시점) 기준 오름차순 정렬 ② 비활성 시점 같으면 생명력 기준 내림차순 정렬 => 큐에서 꺼낼 때, 먼저 발현하는(비활성 시점 작은 순서) 세포들부터 나오게 되고, 비활성 시점이 같으면 생명력이 높은 세포부터 나오게 된다. 🧐 비활성 시점이 같을 때, 서로 다른 위치라면 생명력 비교할 필요 없이 각자 그 위치에 들어가면 되는 것 아닌가? ✅ 같은 표에 도달할 때만 생명력 값 비교가 필요한데, 비활성 시점 기준으로 오름차순으로 되어있으면 같은 좌표라도 먼저 비활성되는 세포가 먼저 나온다.("비활성 시간순서"가 중요⭐️) 같은 좌표, 비활성시점까지 똑같으면 생명력 정렬 기준에 따라 생명력이 큰 세포가 우선순위가 높아서 먼저 나온다. 우선순위 큐 사용할 때, 클래스 생성할 때 implements Comparable<Cell>, compareTo(o) 이용하여 정렬 기준 만든다. 아래 2개씩 주석처리된 리턴문은 모두 정답이다. 그런데 Integer.compare(o.life,life)로 하는 것이 메모리를 조금 덜 차지하는 것 같다. 암튼 그러하다.

   1. static class Cell implements Comparable<Cell> {
              int r, c;// row, col,
              int life; // 살아있는 시간,
              int time;// 턴을 확인하기 위한 값
        
              public Cell(int r, int c, int life, int time) {
                  this.r = r;
                  this.c = c;
                  this.life = life;
                  this.time = time;
              }
        
              public int compareTo(Cell o) {
                  if (this.time == o.time) {
                      //return Integer.compare(o.life, life);
                      return o.life-this.life;
                  } else {
                      //return Integer.compare(this.time, o.time);
                      return this.time-o.time;
                  }
              }
          }

3. 세포의 유무를 저장하는 boolean 타입의 2차원 배열

알고리즘 비활성 시점time 기준으로 배양하는 BFS 진행한다. 큐에서 세포 하나씩 꺼내서 세포 죽는 시점과 K비교를 통해 ans 증가시킨다.

if(time+2*X) ans++;

비활성 시점+2X=죽는 시점이고, 죽는 시점이 K보다 크다는 것은 K시간이 지난 후에 존재한다는 것이므로 ans 1증가시킨다.

배양하는 그리드 크기는 무한대이고, 구하고자 하는 것은 K시간 이후에 살아있는 세포(활성+비활성) 총 갯수이므로 반복문은 무한 루프로 구성하고, 현재 세포의 비활성 시점(발현하는 시점)이 K보다 크면 반복을 종료한다. K보다 크면 활성 시점이나 죽는 시점 또한 K보다 크기 때문에 더이상 반복할 필요 없기 때문이다.

일단 기본 반복문 뼈대는 다음과 같다. 큐에는 살아있는 세포를 저장하여 BFS로 배양을 반복한다. 아래 반복문은 세포의 비활성 시점 기준으로 전개된다.

아래 코드에서 while 반복문 조건(time)이 반복문 내에서 갱신되는 것을 보면 알 수 있듯이, 반복문 조건은 의미없다. while 반복 조건에 true를 넣어도 아래 반복 종료 break문에 의해 정상적으로 돌아간다. 그냥 형식상 해준 것 같다.

int time = 0;
Cell cur;
while(time <= K){
    cur = liveCeells.poll(); 
    if(cur.time > K) break;
    
    for(int d=0;d<4;d++) {
    ...
    }