티스토리 뷰

알고리즘/SW Expert

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

머어하지 2018. 9. 20. 01:18

생각

줄기세포배양 시뮬레이션을 만드려고한다. 각 줄기세포는 생명력을 가지고 있다. 처음 배양의 크기는 세로 N 가로 M으로 주어지고 배양 시간은 K로 주어진다. 세포의 생명력이 X일 경우 해당 세포는 X초 뒤 활성화 뒤어 상하좌우로 번식을 한다(동시에 같은 셀에 번식을 할 경우 높은 생명력을 가진 세포가 번식한다). 그리고 다시 X초 뒤에 해당 세포는 죽는다.

이때 첫 상태가 주어지고 K 시간이 지났을 때, 살이있는 세포의 수(활성 + 비활성)를 구하여라. 배양 용기의 크기는 무한하다.


처음 생각

처음에 딱 최대 크기가 적혀있지 않아 배열의 크기를 어떻게해야하나 고민을 하였다.


다음 생각

우선 시간, 생명력, 생명력이 깍이면서 변하는 숫자, 좌표 등의 정보가 있어야 하므로 Pair class를 따로 만들어주었다.

이 후, 배열의 크기를 정하고 나서 BFS를 이용하여 문제를 풀었다. 이 때, 세포의 생명력이 높으면 해당 세포가 먼저 번식해야 하므로, 맨 처음 입력을 받을 때 List를 생명력(0~9) 별로 만들어 해당 List가 큰 순서로 Queue에 넣어주었다. 후에 생각해보면 굳이 이렇게 하지는 않았어도 됐다.


다다음 생각

Queue의 while문을 탈출하기 위해 단계별로 주어진 시간 K를 깍아가면서 0이 되면 반복문을 break 하도록 하였다.


다다다음 생각

처음에 문제를 잘 못 이해하여 세포가 활성화 된 후, 번식을 하고 바로 죽음으로 처리하였었다. 현 생명력 상태를 다시 원래 생명력만큼 돌려준 뒤 다음번 0이 되었을 때, 번식해야하는가 죽어야하는가를 위해서 각각 세포마다 flag를 추가해주었다.


다다다다음 생각

시간이 0이 되었을 때, 각각의 세포의 할일은 끝났지만 죽은 세포들을 처리해 주기위해서 continue를 사용하여 queue를 비어주었다. 


다다다다다음 생각

위에까지 구현하고나서 테스트 케이스가 잘 되는것을 확인한 후, 제출을 했더니 50개중 48개가 맞았었다. 2개의 예외를 찾기위해 1시간 이상 소비하였지만 도저히 못찾겠어서 질문을 올려볼 까 생각을 하던 그 때, 찾아버렸다!

▶ 세포의 죽음 표시를 위해서 죽었을 경우 해당 세포가 7로 변경되도록 하였는데, 생명력이 0~9 까지이므로 케이스중 2개가 7이 존재하던 케이스 일것 같다. 7로 죽음표시를 하던 것을 -1로 바꾸었더니 정상적으로 PASS 하였다.




방안

1) 세포가 가장 많이 번식하는 것은 바로 모두 생명력이 1인 경우 제일 멀리까지 번식을 할 것이다. 1인 세포가 번식을 하는데 필요한 2시간은 2초이므로 (활성 1초, 번식 1초) 한 쪽 방향으로 계속 번식할 경우 최대로 뻗어나갈 수 있는 길이는 K/2가 된다. K/2가 양쪽으로 적용하면 K가 되므로 배열의 크기를 N+K와 M+K로 정하여 주었다.


2) 배열을 정해준 뒤, 정 가운데에 초기 상태를 넣어주어야 한다. Index가 0부터 시작하므로 K/2 ~ K/2+N or M 으로 조건을 정해주어 초기 상태를 넣어주었다.


3) 처음 상태를 생명력 순으로 넣어주기 위해 List를 사용해서 미리 여러개로 정리를 하였는데, PriorityQueue를 사용했으면 좀 더 구현했을 것 같다. (1)번 코드로 진행할 경우 진행은 제대로하지만 출력을 해보면 시간이 Queue에 들어가는 순서로 나오므로 살짝 들쭉날쭉하다. 따라서 우선 순위 큐를 이용해서 (2)번 처럼 구현하는게 더 올바른것 같다.


(1) 일반 Queue를 이용하여 구현(높은 생명력이 먼저 들어갈 수 있도록 List를 이용하였다)


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static int n,m,k;
    static int[][] arr;
    static List<ArrayList<Pair>> list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for(int i=1;i<=tc;i++) {
            list.clear();
            for(int j=0;j<10;j++)
                list.add(new ArrayList<>());
             
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            arr = new int[n+k][m+k];
            for(int j=(k/2);j<(k/2)+n;j++) {
                st = new StringTokenizer(br.readLine());
                for(int z=(k/2);z<(k/2)+m;z++) {
                    arr[j][z] = Integer.parseInt(st.nextToken());
                    if(arr[j][z]!=0)
                        list.get(arr[j][z]-1).add(new Pair(j, z, arr[j][z], arr[j][z],k,0));
                }
            }
            solve();
            int result = 0;
            for(int j=0;j<arr.length;j++) {
                for(int z=0;z<arr[0].length;z++) {
                    if(arr[j][z]!=0&&arr[j][z]!=-1)
                        result++;
                }
            }
            sb.append("#"+i+" "+result+"\n");
        }
        System.out.print(sb);
    }
     
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve() {
        Queue<Pair> queue = new LinkedList<>();
        for(int i=9;i>=0;i--) {
            if(list.get(i).size()!=0) {
                for(int j=0;j<list.get(i).size();j++) {
                    int x = list.get(i).get(j).x;
                    int y = list.get(i).get(j).y;
                    int k = list.get(i).get(j).k;
                    int time = list.get(i).get(j).time;
                    queue.add(new Pair(x, y, k, k,time,0));
                }
            }
        }
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            if(t.state==0&&t.flag==1) {
                arr[t.x][t.y] = -1;
                continue;
            }
            if(t.time==0) continue;
            if(t.state==0) {
                queue.add(new Pair(t.x,t.y,t.k,t.k,t.time,1));
            } else {
                queue.add(new Pair(t.x, t.y, t.k,t.state-1,t.time-1,t.flag));
                continue;
            }
            for(int i=0;i<4;i++) {
                int tx = t.x+dir[i][0];
                int ty = t.y+dir[i][1];
                if(tx<0 || ty<0 || tx>=n+k || ty>=m+k) continue;
                if(arr[tx][ty]!=0) continue;
                arr[tx][ty] = t.k;
                queue.add(new Pair(tx, ty, t.k, t.k,t.time-1,0));
            }
        }
    }
     
    static class Pair{
        private int x,y,k,state,time,flag;
        public Pair(int x,int y,int k,int state,int time,int flag) {
            this.x = x;
            this.y = y;
            this.k = k;
            this.state = state;
            this.time = time;
            this.flag = flag;
        }
    }
}
cs



(2) PriorityQueue를 이용한 구현


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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Solution {
    static int n,m,k;
    static int[][] arr;
    static List<Pair> list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for(int i=1;i<=tc;i++) {
            list.clear();
             
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            arr = new int[n+k][m+k];
            for(int j=(k/2);j<(k/2)+n;j++) {
                st = new StringTokenizer(br.readLine());
                for(int z=(k/2);z<(k/2)+m;z++) {
                    arr[j][z] = Integer.parseInt(st.nextToken());
                    if(arr[j][z]!=0)
                        list.add(new Pair(j, z, arr[j][z], arr[j][z],k,0));
                }
            }
            solve();
            int result = 0;
            for(int j=0;j<arr.length;j++) {
                for(int z=0;z<arr[0].length;z++) {
                    if(arr[j][z]!=0&&arr[j][z]!=-1)
                        result++;
                }
            }
            sb.append("#"+i+" "+result+"\n");
        }
        System.out.print(sb);
    }
     
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve() {
        PriorityQueue<Pair> queue = new PriorityQueue(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.time>o2.time?-1:o1.time==o2.time?o1.k>o2.k?-1:1:1;
            }
        });
        for(int i=0;i<list.size();i++)
            queue.add(list.get(i));
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            if(t.state==0&&t.flag==1) {
                arr[t.x][t.y] = -1;
                continue;
            }
            if(t.time==0) continue;
            if(t.state==0) {
                queue.add(new Pair(t.x,t.y,t.k,t.k,t.time,1));
            } else {
                queue.add(new Pair(t.x, t.y, t.k,t.state-1,t.time-1,t.flag));
                continue;
            }
            for(int i=0;i<4;i++) {
                int tx = t.x+dir[i][0];
                int ty = t.y+dir[i][1];
                if(tx<0 || ty<0 || tx>=n+k || ty>=m+k) continue;
                if(arr[tx][ty]!=0) continue;
                arr[tx][ty] = t.k;
                queue.add(new Pair(tx, ty, t.k, t.k,t.time-1,0));
            }
        }
    }
     
    static class Pair{
        private int x,y,k,state,time,flag;
        public Pair(int x,int y,int k,int state,int time,int flag) {
            this.x = x;
            this.y = y;
            this.k = k;
            this.state = state; // 변하는 생명력
            this.time = time;
            this.flag = flag; // 0이 되었을 때, 번식 했나 유무
        }
    }
}
cs



'알고리즘 > SW Expert' 카테고리의 다른 글

[SW Expert] 5656. [모의 SW 역량테스트] 벽돌 깨기  (7) 2018.09.27
[SW Expert] 5658. [모의 SW 역량테스트] 보물상자 비밀번호  (0) 2018.09.27
[SW Expert] 4013. [모의 SW 역량테스트] 특이한 자석  (0) 2018.09.16
[SW Expert] 4014. [모의 SW 역량테스트] 활주로 건설  (0) 2018.09.16
[SW Expert] 5432. 쇠막대기 자르기  (0) 2018.09.06
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday