[SWEA] 5653. 줄기세포배양

BFS를 이용하여 구현하는 문제이다.

이 문제에서 유의할게 여러가지 있었다. 갱신을 하는 과정에서 생명력 수치가 높은 줄기 세포가 그리드 셀을 차지 하는 것,  X시간 동안 비활성 상태를 거치고 X시간이 지나는 순간 X시간 동안 활성상태가 되는 것, 맵의 크기가 제대로 주어지지 않는 점등 구현에 까다로운 점이 많았다. 다음과 같이 해결하였다.

생명력 수치가 높은 세포로 갱신 -> PriorityQueue를 이용하여 생명력이 높은 세포들이 가장 위에 올수있도록 사용
X시간 후 X시간 동안 활성 -> curLive가 0이 되기전까지 계속 PrioirtyQueue에 남겨두기
맵의 크기 -> 주어진 r,c값에 time*2를 더해준 만큼 크기를 잡기

구현의 고려요소가 많아서 상당히 오랜시간을 풀었고, 많은 것을 참조하여 풀었다. 다시풀어봐야할 문제인 것 같다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution_5653_줄기세포배양 {
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int R;
    static int C;
    static int time;
    
    static boolean[][] check;
    
    static PriorityQueue<Pos> pq;
    static Queue<Pos> temp;
    
    static class Pos implements Comparable<Pos>{
        int i,j,originalLife,curLife;
        Pos(int i,int j,int o,int c){
            this.i=i;this.j=j;originalLife=o;curLife=c;
        }
        @Override
        public int compareTo(Pos o) {
            return -Integer.compare(originalLife, o.originalLife);
        }
    }
    
    public static void main(String[] args) throws Exception {
        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());
            int r= Integer.parseInt(st.nextToken());
            int c= Integer.parseInt(st.nextToken());
            time= Integer.parseInt(st.nextToken());
            
            R=r+time*2+4;
            C=c+time*2+4;
            
            check=new boolean[R][C];
            pq=new PriorityQueue<>();
            temp=new LinkedList<>();
            
            for(int i=R/2-1;i<R/2-1+r;i++) {
                st=new StringTokenizer(br.readLine());
                for(int j=C/2-1; j<C/2-1+c;j++) {
                    int num=Integer.parseInt(st.nextToken());
                    if(num!=0) {
                        check[i][j]=true;
                        pq.offer(new Pos(i, j, num, num*2));
                    }
                }
            }
            
            func();
            System.out.println("#"+tc+" "+pq.size());
            
        }
    }
    
    static void func() {
        for(int t=1;t<=time;t++) {
            
            while(!pq.isEmpty()) {
                Pos cur =pq.poll();
                
                cur.curLife=cur.curLife-1;
                
                if(cur.originalLife> cur.curLife) {    //활성화
                    for(int dir=0;dir<4;dir++) {
                        int nextI=cur.i+di[dir];
                        int nextJ=cur.j+dj[dir];
                        
                        if(nextI<0 ||nextI>=R || nextJ<0 ||nextJ>=C)
                            continue;
                        
                        if(check[nextI][nextJ]==false) {
                            check[nextI][nextJ]=true;
                            temp.offer(new Pos(nextI, nextJ, cur.originalLife, cur.originalLife*2));
                        }
                    }
                }
                
                
                if(cur.curLife!=0) {    //안죽은 경우
                    temp.offer(new Pos(cur.i, cur.j, cur.originalLife, cur.curLife));
                }
                
            }
            
            while(!temp.isEmpty()) {
                pq.offer(temp.poll());
            }
            
        }
        
        
    }
}