<SWEA> #5653 줄기세포배양 java

Google 아니고 Joogle·2022년 10월 3일
0

SAMSUNG SW Test

목록 보기
39/39

SWEA #5653 줄기세포배양

Solution

  • 배양 용기의 크기는 무한하다고 가정하였기 때문에 map을 따로 두지 않고 그냥 좌표로만 관리하였더니 시간 초과가 났다 → 초기 줄기 세포 영역의 넓이가 NxM 이고, 배양 시간은 최대 K이기 때문에 map의 크기를 [N+2*K][M+2*K] 로 두고 좌표를 다시 관리했다.

1. class Cell

  • cell class의 구조는 다음과 같다
  • cell이 있는 좌표 (y,x), cell의 생명력 (power), cell의 상태 변화가 일어나는 시간 (time)
  • cell의 상태DEAD, ACTIVE, INACTIVE 3가지로 구분하여 관리한다
    (static final int DEAD=0, ACTIVE=1, INACTIVE=2;)
	static class Cell {
		int y,x,time,state,power;
		
		Cell (int y, int x, int time, int power) {
			this.y=y;
			this.x=x;
			this.time=time;
			this.power=power;
			this.state=INACTIVE;
		}		
	}

2. List< Cell>, PriorityQueue< Cell>

  • 모든 cell은 List<Cell> cell 에 넣어 관리해준다
  • 추가로 PriorityQueue pq=new PriorityQueue<>( (p1, p2) -> p2.power-p1.power) 를 만들어 관리해주었는데 이 pq의 용도는 다음과 같다

    7시간 후에 파란색 cell들이 활성 상태가 되었을 때, 1시간 후(8시간 째)에 활성 상태 cell을 기준으로 상하좌우로 새로운 비활성 상태의 cell들이 생겨난다.
    이때 문제 조건 중, "두 개 이상의 줄기 세포가 하나의 그리드 셀에 동시 번식하려고 하는 경우, 생명력 수치가 높은 줄기 세포가 해당 그리드 셀을 혼자 차지 하게 된다" 라는 조건이 있다.
    따라서 생명력이 높은 cell이 높은 우선순위를 가지는 우선순위큐를 만들어 주고, 활성상태로 된 cell 주변으로 새로 생기는 cell들을 우선순위큐에 넣어준다.
    그리고 1시간이 지났을 때, 우선 순위가 높은 cell 먼저 자리를 차지하게 된다

3. cell 상태 변경

  • 현재 시간 k일 때, cell의 상태에 따라서 상태 변경이 일어난다
	for (int i=0; i<cell.size(); i++) {
		if (cell.get(i).state==DEAD) continue;
				
		else if (cell.get(i).state==INACTIVE && cell.get(i).time==k) {
			cell.get(i).state=ACTIVE;				// X시간동안 활성상태
			cell.get(i).time=k+cell.get(i).power;	// 현재 시간 보다 X 시간이 지난 후에 죽는 상태로 만들어줄 것
					
					
			for (int d=0; d<4; d++) {
				// k+1+power 후에 변경상태가 될 것
				int ny=cell.get(i).y+dy[d];
				int nx=cell.get(i).x+dx[d];
						
				pq.add(new Cell(ny,nx, k+1+cell.get(i).power, cell.get(i).power));
			}
					
		} else if (cell.get(i).state==ACTIVE && cell.get(i).time==k) {
			cell.get(i).state=DEAD;
			cell.get(i).time=0;
			cell.get(i).power=0;
		}			
	}
  1. cell이 죽은 상태라면 그냥 넘어간다
  2. cell의 상태가 비활성 상태이고, 현재 시간 k와 cell의 time (변경이 일어날 시간)이 같다면, cell을 활성 상태로 만들어주고, 다음 변경이 일어날 시간은 (k+cell의 생명력 수치)로 바꾸어준다
  3. 위에서 활성 상태가 된 cell 기준으로 상하좌우에 새로 생길 cell들은 현재시간 +1 (k+1) 시간에 새로 생길 것이기 때문에 (k+1+cell의 생명력 수치) 로 설정
    4. cell의 상태가 활성 상태이고, 현재 시간 k와 cell의 time이 같다면 cell을 죽여준다

Source Code

package bfs.dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class SWEA5653 {

	static final int dy[]= {0,0,1,-1};
	static final int dx[]= {1,-1,0,0};
	
	static final int DEAD=0, ACTIVE=1, INACTIVE=2;
	static int T,N,M,K;
	
	static List<Cell> cell;
	static PriorityQueue<Cell> pq;
	static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st=null;
		
		T=Integer.parseInt(br.readLine());
		
		for (int tc=1; tc<=T; tc++) {
			st=new StringTokenizer (br.readLine());
			N=Integer.parseInt(st.nextToken());
			M=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			
			cell=new ArrayList<>();
			pq=new PriorityQueue<>( (p1, p2) -> p2.power-p1.power );
			visited=new boolean[N+2*K][M+2*K];
			
			
			for (int i=0; i<N; i++) {
				st=new StringTokenizer (br.readLine());
				for (int j=0; j<M; j++) {
					int n=Integer.parseInt(st.nextToken());
				
					if (n!=0) {
						cell.add(new Cell(i+K,j+K,n,n));
						visited[i+K][j+K]=true;
					}

				}
			}
			simulation();
			System.out.println("#"+tc+" "+count());
				
		}
	}
	
	static void simulation () {
		for (int k=1; k<=K; k++) {
			
			// 직전에 INACTIVE -> ACTIVE 상태로 변경된 cell들 
			while (!pq.isEmpty()) {
				Cell c=pq.poll();
				int y=c.y;
				int x=c.x;
				
				if (!visited[y][x]) {
					visited[y][x]=true;
					cell.add(c);
				}
			}
			
			for (int i=0; i<cell.size(); i++) {
				if (cell.get(i).state==DEAD) continue;
				
				else if (cell.get(i).state==INACTIVE && cell.get(i).time==k) {
					cell.get(i).state=ACTIVE;				// X시간동안 활성상태
					cell.get(i).time=k+cell.get(i).power;	// 현재 시간 보다 X 시간이 지난 후에 죽는 상태로 만들어줄 것
					
					
					for (int d=0; d<4; d++) {
						// k+1+power 후에 변경상태가 될 것
						int ny=cell.get(i).y+dy[d];
						int nx=cell.get(i).x+dx[d];
						
						pq.add(new Cell(ny,nx, k+1+cell.get(i).power, cell.get(i).power));
					}
					
				} else if (cell.get(i).state==ACTIVE && cell.get(i).time==k) {
					cell.get(i).state=DEAD;
					cell.get(i).time=0;
					cell.get(i).power=0;
				}
				
			}
		}
	}
	
	static int count () {
		int cnt=0;
		for (int i=0; i<cell.size(); i++) {
			if (cell.get(i).state==ACTIVE || cell.get(i).state==INACTIVE)
				cnt++;
		}
		return cnt;
	}
	
	
	static class Cell {
		int y,x,time,state,power;
		
		Cell (int y, int x, int time, int power) {
			this.y=y;
			this.x=x;
			this.time=time;
			this.power=power;
			this.state=INACTIVE;
		}		
	}
}

profile
Backend 개발자 지망생

0개의 댓글