줄기세포배양


Software Expert Academy [5653] 줄기세포배양

문제보기
Alt text

풀이

  • 동시 번식 : time으로 해결
  • 주의사항 : for문으로 다 돌아서 (1≤K≤300) 이고 1000*1000으로 했을 경우 시간초과가 났다.
  • 해결방법 : X와 Y를 0,0 부터 시작하는게 아니라 셀들이 존제하는 최소 인덱스에서 시작하고 700*700으로 해봄
  • Queue를 사용해서 풀이하는게 좋을 것 같다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static class Cell {
        int x;
        int condition;
        int t; // 몇초에 생긴 녀석인지
        int actT; // 몇초에 활성된 녀석인지
 
        public Cell(int x, int condition, int t, int actT) {
            this.x = x;
            this.condition = condition; // 0:비활,1:활,2:죽음
            this.t = t;
            this.actT = actT;
        }
    }
 
    static Cell[][] map;
    static int N, M, K, ans;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static int X, Y;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            ans = 0;
            map = new Cell[700][700];
 
            int r = map.length / 2;
            int c = map[0].length / 2;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    int x = Integer.parseInt(st.nextToken());
                    if (x != 0) {
                        ans++;
                        map[r][c] = new Cell(x, 0, 0, 0);
                    }
                    c++;
                }
                c = map[0].length / 2;
                r++;
            }
 
            X = map.length / 2;
            Y = map[0].length / 2;
 
            for (int i = 0; i <= K; i++) {
                raise(i);
            }
            System.out.println("#" + tc + " " + ans);
        }
    }
 
    public static void raise(int time) {
        int minX = X;
        int minY = Y;
        for (int i = X; i < map.length; i++) {
            for (int j = Y; j < map[i].length; j++) {
                if (map[i][j] != null) {
                    if (map[i][j].x != 0 && map[i][j].condition != 2) {
                        if (map[i][j].condition == 0) { // 비활
                            if (map[i][j].x == time - map[i][j].t) {
                                map[i][j].condition = 1;
                                map[i][j].actT = time;
                            }
                        } else { // 활성
                            for (int k = 0; k < 4; k++) {
                                int r = i + dx[k];
                                int c = j + dy[k];
 
                                if (minX > r)
                                    minX = r;
                                if (minY > c)
                                    minY = c;
 
                                if (map[r][c] == null) {
                                    map[r][c] = new Cell(map[i][j].x, 0, time, map[i][j].actT);
                                    ans++;
                                } else {
                                    if (map[r][c].t < time)
                                        continue;
                                    else if (map[r][c].t == time) { // 동시번식
                                        if (map[r][c].x < map[i][j].x) {
                                            map[r][c].x = map[i][j].x;
                                        }
                                    }
                                }
                            }
                            if (map[i][j].x == time - map[i][j].actT) { // 이미 활성끝
                                map[i][j].condition = 2;
                                ans--;
                            }
                        }
                    }
                }
            }
        }
        X = minX;
        Y = minY;
    }
}