SWEA[5653] - 줄기세포배양

링크

SWEA[5653]

문제설명

• 시뮬레이션

문제풀이

• 시뮬레이션

문제코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {

    public static int[][] dir = {  //
            {-1,0},                //상
            {1,0},                 //하
            {0,-1},                //좌
            {0,1},                 //우
    };
    public static int Ans=0;
    public final static int MAX = 350;
    public static int N;
    public static int M;
    public static int K;
    public static int[][] life         ;        //{life}
    public static int[][] life_next ;        //{life}
    public static int[][] count     ;    //{>0:비활성,0:활성 }

    public static void count_minus() {
        for (int i = 0; i < N+K; i++) {
            for (int j = 0; j < M+K; j++) {
                if(life[i][j]!=0) {
                    count[i][j]--;
                }
            }
        }
    }

    public static void spread(int r, int c) {
        int nr=0;
        int nc=0;
        //활성화 된 세포일 경우 옆에 퍼트린다.
        if(life[r][c]>0 && count[r][c]==0) {
            for (int i = 0; i < 4; i++) {
                nr = r+ dir[i][0];
                nc = c+ dir[i][1];
                //퍼트릴수 있을 경우.{세포가 없음}
                if(nr>=0 && nr<N+K && nc>=0 && nc<M+K && life[nr][nc] == 0) {
                    if(life_next[nr][nc]<life[r][c]) {    //퍼트릴때 자기 life가 더 강하면 덮어씌운다.
                        life_next[nr][nc]=life[r][c];
                    }
                }
            }
        }
        return;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        //System.setIn(new FileInputStream("res/swea/5653.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T=Integer.parseInt(br.readLine());
        StringTokenizer st;

        for (int test_case = 1; test_case <= T; test_case++) {
            // 입력
            st = new StringTokenizer(br.readLine()," ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            life         = new int[N+K][M+K];
            life_next = new int[N+K][M+K];
            count     = new int[N+K][M+K];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine()," ");
                for (int j = 0; j < M; j++) {
                    life[(K/2) + i][(K/2) + j] = Integer.parseInt(st.nextToken());
                    count[(K/2) + i][(K/2) + j] = life[(K/2) + i][(K/2) + j];
                }
            }

            for (int k = 1; k <= K; k++) {
                //spread
                for (int i = 0; i < N+K; i++) {
                    for (int j = 0; j < M+K; j++) {
                        spread(i, j);
                    }
                }
                //int debug=0;
                //life_next에 있는것 life로 이동
                for (int i = 0; i < N+K; i++) {
                    for (int j = 0; j < M+K; j++) {
                        if(life_next[i][j]!=0) {
                            life[i][j]=life_next[i][j];
                            count[i][j]=life[i][j]+1;    //map count -- 할꺼라서
                            life_next[i][j]=0;
                        }
                    }
                }

                //count--
                count_minus();
            }
            //count ans
            for (int i = 0; i < N+K; i++) {
                for (int j = 0; j < M+K; j++) {
                    if((life[i][j]+count[i][j])>0) {    //세포들 중에 활성, 비활성인 세포들 ( 죽은애들은 음의 값을 가짐) 
                        Ans++;
                    }
//                    life[i][j]=0;
//                    count[i][j]=0;
                }
            }
//            bw.write("#"+test_case+" "+Ans);
            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
        }//end test_case
    }//end main
}

아쉬운점

• Spread할 경우 탐색도중에 세포가 생성되기때문에 생성된세포를 또 탐색하는 경우가 생김
  • 배열을 2개 만들고 옮기기하는 방식으로 해결
• 세포를 기준으로 탐색하지않고, 퍼질 수 있는 공간을 기준으로 탐색을 하는 경우 시간초과가 뜸.
  • O(N) 고려 해 봐야 할 것 같음.
    • 세포기준 탐색경우 : 세포의 갯수만큼만 탐색 가능
    • 빈칸기준 탐색경우 : 빈칸에서 4방향check 모두 하기 때문에 배열전체만큼 탐색해야함. 시간 걸릴만함.

잘한점

• 예전에는 못풀었는데 품
• 디버깅 편하게하려고 구조체말고 그냥 배열로 했음
• 배열의 크기를 Input에 맞게 동적으로 변경(시간초과 방지)
• 답은 나왔음