SWEA 5653 [줄기세포배양]

SW Expert Academy 줄기세포배양 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo

//SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다.

안녕하세요. 이번 문제는 SW Expert Academy의 줄기세포배양 입니다.

간략하게 설명하자면, 범위가 한정되지 않는 그리드에 줄기세포가 뻗어나가도록 하는 문제입니다.

삼성 SWEA에서 주관하는 A형 SW역량테스트에 나온 문제가 떠올랐습니다.

먼저 다음을 설정해 줬습니다.

1. 세포가 그리드의 제한 없이 뻗어나가기 때문에, padding 사이즈를 위, 아래, 좌, 우 각각 150만큼 늘렸습니다.

2. Cell 클래스 : 세포의 좌표, 현재 진행된 시간, 초기생명, 세포의 남은 생명

그리고 문제 해결 방법입니다.

1. 큐에 현재 세포들을 넣는다.

2. 세포의 생명력이 0 이상이면, 생명력을 깎으며 다시 큐에 담은 뒤, 스킵.

3. 세포의 생명력이 0 이면, 활성 상태에 돌입하는 자신을 큐에 담은 뒤, 4 방향을 탐색.

이때, 처음 방문하는 좌표일 시 Visited를 true로 설정하고,

처음 방문이 아니면서, 동일 시간에 접근한 좌표일 시, 더 높은 초기값을 해당 좌표의 세포 값으로 설정.

4. 세포의 생명력이 -초기 상태가 될때까지 활성상태로 남겨둔다.

저같은 경우, 세포가 뻗어나가면 해당 세포(활성 세포)를 바로 죽여버려서 (미안해 세포들아,,,) 

따로 카운트하지 않아 계속 Fail이 나왔었습니다.

활성 세포를 계속 죽은 세포 취급하면, 3번째 테스트케이스에서 70이 나옵니다...

문제를 제대로 이해하는게 가장 중요한 것 같습니다.

   

import java.util.*;
 
class Cell {
    public int i, j, time, life;
    public boolean init;
    public Cell(int i, int j, int time, int life, boolean init) {
        this.i = i;
        this.j = j;
        this.time = time;
        this.life = life;
        this.init = init;
    }
}
public class Solution {
    public static int T;
    public static int N, M, K;
    public static int[][] Grid = new int[350][350];
    public static int[][] depth = new int[350][350];
    public static boolean[][] Visited = new boolean[350][350];
    public static int[][] d = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    public static Queue<Cell> q = new LinkedList<Cell>();
    public static int BFS() {
        int result = 0;
        while(!q.isEmpty()) {
            Cell cell = q.poll();
            if(cell.life == -Grid[cell.i][cell.j])
                continue;
            if(cell.time == K) {
                result++;
                continue;
            }
            if(cell.init) {
                cell.life = Grid[cell.i][cell.j];
            }
            if(cell.life > 0) {
                Cell new_cell = new Cell(cell.i, cell.j, cell.time + 1, cell.life - 1, false);
                q.offer(new_cell);
                continue;
            }
            else if(cell.life == 0) {
                Cell c = new Cell(cell.i, cell.j, cell.time + 1, cell.life -1, false);
                q.offer(c);
                for(int k = 0; k < 4; k++) {
                    int next_i = cell.i + d[k][0];
                    int next_j = cell.j + d[k][1];
                    if(!Visited[next_i][next_j]) {
                        Visited[next_i][next_j] = true;
                        Grid[next_i][next_j] = Grid[cell.i][cell.j];
                        depth[next_i][next_j] = cell.time + 1;
                        Cell new_cell = new Cell(next_i, next_j, cell.time + 1, cell.life, true);
                        q.offer(new_cell);
                    }
                    else if(Visited[next_i][next_j] && depth[next_i][next_j] == cell.time + 1) {
                        if(Grid[next_i][next_j] < Grid[cell.i][cell.j])
                            Grid[next_i][next_j] = Grid[cell.i][cell.j];
                    }
                }
            }
            else if(cell.life != -Grid[cell.i][cell.j]) {
                Cell new_cell = new Cell(cell.i, cell.j, cell.time + 1, cell.life - 1, false);
                q.offer(new_cell);
                continue;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for(int test_case = 1; test_case <= T; test_case++) {
            N = sc.nextInt();
            M = sc.nextInt();
            K = sc.nextInt();
            for(int i= 0; i<N; i++) {
                for(int j =0; j < M; j++) {
                    Grid[150 + i][150 + j] = sc.nextInt();
                    if(Grid[150+i][150 + j] != 0) {
                        Visited[150 + i][150 + j] = true;
                        depth[150 + i][150 + j] = 0;
                        Cell cell = new Cell(150 + i, 150 + j, 0, Grid[150 + j][150 + j], true);
                        q.offer(cell);
                    }
                }
            }
            System.out.println("#" + test_case + " " + BFS());
            for(int i = 0; i < 350; i++) {
                for(int j = 0; j< 350; j++) {
                    Grid[i][j] = 0;
                    Visited[i][j] = false;
                    depth[i][j] = 0;
                }
            }
        }
    }
}