[SW Expert] [모의 SW 역량테스트] 5653번 줄기세포배양 (Java)

 

 

SW Expert [모의 SW 역량테스트] 5653번 줄기세포배양 : 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo

 

 

'배양 용기의 크기는 무한하다'는 조건 때문에 고민을 많이 했던 문제이다.

처음에는 세포들의 정보만 클래스로 저장하여 조작해보려 했지만,

같은 위치에 2개 이상의 세포들이 증식할 때 생명력 수치를 몇으로 해야 할지 고민을 하다가 접었다.

배열로 처리할 방법이 없을까 고민을 하다가 K 시간 동안 최대 얼마나 번져 나갈 수 있을지 계산하였다.

세포의 생명력 수치가 1이라고 치면 1번 증식하는데 2시간이 걸린다.

생명력 수치가 1인 세포가 가장 빨리 증식하게 되므로, K 시간 동안 최대 K/2만큼 증식하게 된다.

따라서 배열의 크기를 여유롭게 N+K+2, M+K+2만큼 잡게 되었다.

 

배열의 크기를 잡았다면 풀이 과정은 수월하다.

우선 세포의 정보를 담는 Cell 클래스를 선언해준다.

Cell 클래스에는 좌표 정보, 생명력 수치(value), 상태(status)와 temp라는 변수를 추가로 가진다.

세포는 매 시간마다 생명력 수치를 기준으로 해서 상태가 바뀌게 된다.

생명력 수치가 1인 세포는 1시간 뒤에 상태가 바뀌고, 생명력 수치가 3인 세포는 3시간 뒤에 상태가 바뀐다.

이를 이용해서 세포의 상태 변화는 Cell 클래스에 next 함수를 작성하여 관리하였다.

매 시간마다 next 함수를 호출하게 되며, next 함수가 동작하면 temp 변수를 감소시키거나 증가시킨다.

초기에 temp는 value와 같은 값을 가지며, next 함수가 호출되면 1씩 감소한다.

temp가 0이 된다면 value 값만큼 시간이 흘렀기 때문에 상태를 활성화 상태로 바꿔준다.

그 뒤에는 1씩 증가하기 시작하여 value와 같은 값이 된다면 죽은 상태로 바꿔준다. 

 

증식되는 세포의 value 값을 정해주는 게 조금 까다로웠다.

우선 Queue 안에 들어 있는 모든 세포들을 탐색하여 check 함수로 주변의 value들을 정해준다.

2개 이상의 세포가 같은 위치에 번식된다고 하면 둘 중 큰 값으로 value를 정하게 된다.

그 후, Queue에서 세포들을 꺼내며 활성화 상태인 경우만 주변 세포로 증식을 해준다.

증식된 세포들을 체크해주기 위하여 2차원 boolean 배열(visit)을 사용했다.

 

이번 문제는 생각한 대로 한 번에 돌아가서 뭔가 싶었다.

평소에는 값을 여러 번 출력하면서 계속 수정하면서 풀었는데,

이번에는 테스트 출력하자마자 바로 정답이 나와서 당황스러웠다.

실행시간도 228ms로 빠른 편이라서 기분이 좋다.

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int n, m, k, nx, ny;
    private static int[][] map;
    private static boolean[][] visit;
    private static Queue<Cell> queue = new LinkedList<>();
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};
    private static final short DEATH = 0, ACTIVE = 1, INACTIVE = 2;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            map = new int[n + k + 2][m + k + 2];
            visit = new boolean[n + k + 2][m + k + 2];
            queue.clear();

            int temp;
            for (int i = k / 2 + 1; i < n + k / 2 + 1; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = k / 2 + 1; j < m + k / 2 + 1; j++) {
                    temp = Integer.parseInt(st.nextToken());
                    if (temp != 0) {
                        map[i][j] = temp;
                        visit[i][j] = true;
                        queue.add(new Cell(i, j, temp));
                    }
                }
            }

            int answer = solution();
            System.out.println("#" + t + " " + answer);
        }
    }

    private static int solution() {
        int count = k;
        Cell cell;
        while (count-- > 0) {
            int len = queue.size();
            for (Cell c : queue) {
                if (c.status == ACTIVE) check(c); // 주변에 세포 value 정해줌
            }

            for (int t = 0; t < len; t++) {
                cell = queue.poll();
                if (cell.status == ACTIVE) { // 활성화 상태인 경우만 번식
                    for (int i = 0; i < 4; i++) { // 상하좌우
                        nx = cell.x + dx[i];
                        ny = cell.y + dy[i];

                        if (visit[nx][ny]) continue;

                        queue.add(new Cell(nx, ny, map[nx][ny])); // 번식된 세포 추가
                        visit[nx][ny] = true; // 방문 처리
                    }
                }

                cell.next(); // 세포 상태 변화
                
                if (cell.status == DEATH) continue; // 죽은 세포는 queue에서 제외
                queue.add(cell);
            }
        }
        return queue.size();
    }

    private static void check(Cell cell) {
        for (int i = 0; i < 4; i++) {
            nx = cell.x + dx[i];
            ny = cell.y + dy[i];

            if (visit[nx][ny]) continue;

            if (map[nx][ny] < cell.value) map[nx][ny] = cell.value;
        }
    }

    static class Cell {
        int x, y;
        int value, temp;
        short status;

        public Cell(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.temp = value;
            this.status = INACTIVE;
        }

        public void next() {
            switch (status) {
                case INACTIVE: // 비활성화 상태
                    if (--temp == 0) status = ACTIVE;
                    break;
                case ACTIVE: // 활성화 상태
                    if (++temp == value) status = DEATH;
                    break;
            }
        }
    }
}