공부공간

SWEA ) 줄기세포 배양 본문

알고리즘/구현,시뮬

SWEA ) 줄기세포 배양

개발자가될수있을까? 2020. 2. 9. 00:29

 

왤케 어렵게 생각했었지..

생각보다 단계별로 나누면 간단한 문제였다..

통과된게 신기하지만..

 

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

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

줄기세포는 각 X 시간후에 번식하면서 ( 상 하 좌 우 )

 

X 시간동안 살아있으면서 X 시간이 지나면 죽는 세포분열? 문제이다.

 

1초에는 생명력이 1인 세포들이 번식준비를하고 2초에 상하좌우로 번식하게 된다, 동시에 생명력 2인 세포들이 번식하면서 계속 진행하게 된다.

 

그러면 t초 후에는 어떠한 세포들이 번식을 하게될까?

 

예를 들어 생명력이 1 인 세포가 번식 준비를 하는 시간은

1초 3초 5초... 이런식이다

 

생명력이 2 인 세포는 2초 5초 7초..

2초때 생성은 3초에 하므로 5초에 그다음세포가 번식 준비를 한다.

 

3초는 3초 7초 11초..

 

이렇게보면 규칙이 잘 안보이지만 일반화해서 본다면 

생명력 X인 세포는 시간 T에서

 

T  %( X +1 ) == X의 수식을 만족하면 T에서 생명력 X의 세포는 증식한다.

다시 예시를보면

 

7초일때 생명력 3인 세포의 증식여부는

7 % ( 3 +1 ) == 3 으로 증식이 된다는 말이다.

 

간단한 예외로 초기 상태를 0으로 둔다면 X초에 처음으로 세포가 증식한다.

 

이러한 규칙으로 상하좌우로 번식하는문제이다.

 

문제에서 또 특이한점은 Map의 크기는 무한대라고 주어졌다.

사실 기준점인 T가 문제에서 주어지므로 단위시간당 가로 세로는 2씩 증가한다.

 

따라서 문제 제한 조건인 T < 300 가로 세로 50 씩 한다면

651정도의 map이 필요할것이다.

 

넉넉하게 701로 잡고 문제를 풀어보았다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package practice;
 
 
 
public class 줄기세포배양 {
    static int answer = 0;
    static int maxi = 0;
    static int dir[][]= {{1,0},{-1,0},{0,-1},{0,1}};
    
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/ans/줄기세포.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(st.nextToken());
        for(int tc= 1; tc<=t ; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int map_size = 701;
            int map[][] = new int[map_size][map_size];      // 세포의 생존시간을 저장하는 배열
            int Spread[][] = new int[map_size][map_size];// 다음 타임에 번식 할 세포인지 확인하는 배열
            int Born[][] = new int[map_size][map_size];  // 번식후 시간을 확인하는 배열 
            int live[][] = new int[map_size][map_size];  // 세포가 살았는지 죽었는지 확인하는 배열
            for(int y = 0 ; y < n ; y++) {
                st = new StringTokenizer(br.readLine());
                for(int x= 0 ; x <  m ;x++) {
                    map[y + map_size/2][x + map_size/2]= Integer.parseInt(st.nextToken());
                    if(map[y + map_size/2][x + map_size/2]!=0) {
                        live[y + map_size/2][x + map_size/2] = 1; // 0이 아니면 살은 세포
                        
                    }
                }
            }
            for(int time = 1 ; time <= k ; time++) {
                
                for(int y=map_size/2  - n -1  - time; y <= map_size/2 + time + n  +1; y++){
                    for(int x=  map_size/2 - time - m -1 ; x<= map_size/2 + time + m +1  ; x++){
                        if( live[y][x]==1 && ((time % (map[y][x] + 1) == map[y][x]))|| time == map[y][x]) {
                            // 살아있는 애들중에 자기 차례가 되면 다음 시간에 번식 할 세포들
                            Spread[y][x] = 1;
                        }
                    }
                }
                
                for(int y=map_size/2 - time - n -1; y <= map_size/2 + time + n  +1; y++) {
                    for(int x=  map_size/2 - time - m  -1; x<= map_size/2 + time + m  +1  ; x++) {
                        if(live[y][x] == 1 &&Spread[y][x] == 2) { // 살아있고 자기 차례인 애들 번식해야함
                            for(int a = 0 ; a <4 ; a++) {
                                int ny = y +dir[a][0];
                                int nx = x +dir[a][1];
                                if(ny < 0 || nx <0 || ny >= map_size ||nx >= map_size ) continue;
                                if(map[ny][nx] ==0) {
                                    // 동시 번식시 큰쪽이 번식 해야함. 
                                    // 가려는 쪽이 0이면 번식
                                    map[ny][nx] = map[y][x];
                                    live[ny][nx] = 2;
                                }
                                else if(live[ny][nx] == 2  && map[ny][nx] < map[y][x]) {
                                    // 다른 세포가 번식했을 경우, 생존시간이 0 인애들 == 갓 태어난 애들 , 
// 중에서 나보다 작으면 번식가능
                                    map[ny][nx] = map[y][x];
                                    live[ny][nx] = 2;
                                }
                                
                            }
                        }
                    }
                }
                
                
                for(int y=map_size/2 - time - n-1; y <= map_size/2 + time + n +1; y++) {
                    for(int x=  map_size/2 - time - m-1 ; x<= map_size/2 + time + m  +1  ; x++) {    
                        if(live[y][x]==2) {
                            live[y][x] =1;    
                        }
                        if(Born[y][x]== map[y][x]) {
                            // 살아있는 시간이 생존시간하고 같아지면 
                            live[y][x] =0;
                        }
                        if(Spread[y][x] ==1) {
                            //번식 예정인 친구들이 다음 시간에 번식할수 있게 값을 1 늘려준다.
                            Spread[y][x] =2;
                        }
                        if(live[y][x]==1 && Spread[y][x] ==2) {
                            // 살아 있으면 생존 시간을 +1 증가시켜준다
                            // 이 값이 map이랑 같아지면 그 세포는 죽는다.
                            Born[y][x] +=1;
                        } 
                        
                        if(time==k &&live[y][x] == 1) answer++;
                        
                    }
                }
            }
            sb.append("#"+ tc + " "+ answer+"\n");
            answer= 0;
        }
        System.out.println(sb);
    }
}
 
 
  
 
 
  

 

간당간당했다.. 사실 최적화도 안하고 막한거라..

2차원 배열의 내용을 3차원안에 담거나,

for문의 범위를 적절하게 조정하면, 시간을 줄일 수 있다.

 

단위시간당 2씩 증가하고 초기의 n m 으로 위치를 잘잡아준다면..?

힙 영역의 접근을 최소화한다면..?

시간을 줄일 수 있을것 같다

'알고리즘 > 구현,시뮬' 카테고리의 다른 글

Algorithm 풀이를 위한 JAVA 자료구조 정리  (2) 2020.02.10
SWEA ) 대관이의 대량할인  (0) 2020.02.09
BOJ - 14890 ) 경사로  (0) 2020.02.07
Jungol - 1141 ) 불쾌한 날(Bad Hair Day)  (0) 2020.02.03
BOJ - 2798 ) 블랙잭  (0) 2020.01.28
'알고리즘/구현,시뮬' Related Articles more
Comments