5658. [모의 SW 역량테스트] 보물상자 비밀번호

문제 링크

SWEA 5653 줄기세포배양

풀이

자바가 익숙하지 않아서 어려웠던 문제. Comparator 객체를 사용하여 커스텀한 정렬 기준을 갖는 객체를 만드는 법을 마스터 해야겠다.

static Set<String> check;

나는 이 문제를 읽고 해당 칸에 세포가 있는지 없는지를 배열을 통해 확인하는 것이 아니라 HashSet을 사용하였다. 만약 1,-1에 세포가 있다는 것을 표현한다면 “1 -1” 문자열을 set에 넣어서 있음을 나타냈다.

static private class Info{
  int y, x, time, value;
  Info(int y, int x, int time, int value){
    this.y = y;
    this.x = x;
    this.time = time;
    this.value = value;
  }
}

세포의 정보를 Info라는 클래스를 사용하여 저장하였다. y와 x는 위치를 time은 활성화 되는 시간 혹은 죽는 시간을 의미하며 value는 생명력을 의미한다.

active = new PriorityQueue<>(new Comparator<Info>() {
  @Override
  public int compare(Info a, Info b) {
    return Integer.compare(a.time , b.time);
  }
});

deactive = new PriorityQueue<>(new Comparator<Info>() {
  @Override
  public int compare(Info a, Info b) {
    if(a.time == b.time) return Integer.compare(a.value, b.value); 
    return Integer.compare(a.time, b.time);
  }
});
div = new LinkedList<>();

active에는 현재 활성화 되어 있는 세포가 담긴다. 활성화가 끝나는 시간이 작은 순으로 정렬하였다. deactive에는 비활성화 되어 있는 세포가 담긴다. 활성화 되는 시간이 작은 순으로 정렬하였다. 만약 같다면 생명력이 작은 순으로 정렬하였다. 추후 분열할 때 생명력이 높은 세포가 늦게 생명력이 작은 세포의 자리를 뺐어 생명력이 높은 세포가 먼저 자리를 차지하는 식으로 구현햇다. div에는 분열될 세포들이 들어간다.

for(int i=0;i<N;i++) {
  for(int j=0;j<M;j++) {
    if(info[i][j] == 0) continue;
    check.add(makeString(i,j));
    deactive.add(new Info(i,j,info[i][j],info[i][j]));
  }
}

먼저 for문을 돌면서 초기에 비활성화 되어있는 세포들을 deactive라는 배열에 넣는다. 비활성화 세포가 활성화 되는 시간은 생명력만큼이기 때문에 value에 info[i][j]를 넣는다.

while(cur_time < K) {
  cur_time++;
  // 분열
  while(!div.isEmpty()) {
    Info cur = div.pollLast();
    active.add(new Info(cur.y, cur.x, cur_time + cur.value - 1, cur.value));
    for(int i=0;i<4;i++) {
      int ny = cur.y + dy[i], nx = cur.x + dx[i];
      if(check.contains(makeString(ny,nx))) continue;
      check.add(makeString(ny,nx));
      deactive.add(new Info(ny,nx,cur_time + cur.value,cur.value));
    }
  }
  // 죽음 처리
  while(!active.isEmpty() && active.peek().time <= cur_time) active.poll();
  
  // 비활성화 활성화 처리 
  while(!deactive.isEmpty() && deactive.peek().time <= cur_time) {
    Info cur = deactive.poll();
    div.addLast(cur);
  }
}

이후에는 분열 -> 죽음 처리 -> 비활성화 세포 활성화 처리 순으로 진행하여 코드를 짰다. 비활성화 세포를 활성화 할 때는 바로 active에 넣는 것이 아니라 일단은 분열될 세포이기 때문에 div에 넣었다. 대신 시간이 지나고 세포가 분열 되어 active에 들어살 때는 죽는 시간을 cur_time + cur.value에 1을 빼줬다.

System.out.printf("#%d %d\n",test_case,active.size() + deactive.size() + div.size());

비활성화 상태의 세포와 활성화 세포의 수를 구하는 것이기 때문에 active와 deactive의 크기를 리턴하면 된다.

총 코드

import java.util.*;
import java.io.*;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class Solution
{
	static private class Info{
		int y, x, time, value;
		Info(int y, int x, int time, int value){
			this.y = y;
			this.x = x;
			this.time = time;
			this.value = value;
		}
	}
	
	static int N,M,K;
	static int[][] info;
	static PriorityQueue<Info> deactive,active;
	static Deque<Info> div;
	static Set<String> check;
	static int[] dx = {-1,1,0,0}, dy = {0,0,1,-1};
	
	static String makeString(int y, int x) {
		return Integer.toString(y)+" "+Integer.toString(x);
	}
	
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T;
		T=Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			String[] input = br.readLine().split(" ");
			N = Integer.parseInt(input[0]);
			M = Integer.parseInt(input[1]);
			K = Integer.parseInt(input[2]);
			check = new HashSet<>();
			info = new int[N][M];
			active = new PriorityQueue<>(new Comparator<Info>() {
				@Override
				public int compare(Info a, Info b) {
					return Integer.compare(a.time , b.time);
				}
			});

			deactive = new PriorityQueue<>(new Comparator<Info>() {
				@Override
				public int compare(Info a, Info b) {
					if(a.time == b.time) return Integer.compare(a.value, b.value); 
					return Integer.compare(a.time, b.time);
				}
			});
			div = new LinkedList<>();
			
			for(int i=0;i<N;i++) {
				input = br.readLine().split(" ");
				for(int j = 0; j < M;j++) info[i][j] = Integer.parseInt(input[j]);
			}
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(info[i][j] == 0) continue;
					check.add(makeString(i,j));
					deactive.add(new Info(i,j,info[i][j],info[i][j]));
				}
			}
			
			int cur_time = 0;
			
			while(cur_time < K) {
				cur_time++;
				// 분열
				while(!div.isEmpty()) {
					Info cur = div.pollLast();
					active.add(new Info(cur.y, cur.x, cur_time + cur.value - 1, cur.value));
					for(int i=0;i<4;i++) {
						int ny = cur.y + dy[i], nx = cur.x + dx[i];
						if(check.contains(makeString(ny,nx))) continue;
						check.add(makeString(ny,nx));
						deactive.add(new Info(ny,nx,cur_time + cur.value,cur.value));
					}
				}
				// 죽음 처리
				while(!active.isEmpty() && active.peek().time <= cur_time) active.poll();
				
				// 비활성화 활성화 처리 
				while(!deactive.isEmpty() && deactive.peek().time <= cur_time) {
					Info cur = deactive.poll();
					div.addLast(cur);
				}
			}
			
			System.out.printf("#%d %d\n",test_case,active.size() + deactive.size() + div.size());
			

		}
	}
}