[SWEA] 5653.줄기세포배양(모의 SW 역량테스트) - JAVA

SWEA에서 모의 역량테스트 문제 풀어보다가 신기한?흥미로운? 문제를 발견해서 적어보려고한다.

또, 내가 푼 방법은 다른사람들이 주로 푼 방법과는 달라서 두가지 방법을 모두 정리해보려한다.

 

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

내 풀이

일단, 문제를 처음 읽고 든 생각은.. 배양 용기의 크기가 무한하다고 가정해야하고, 배열이 계속해서 커지는데 어떻게 풀지?

심지어 배열이 상하좌우로 알수없게 커진다는점이 고민을 하게 만들었고,,

결국 난 배열이 아니라, 해시맵을 이용해서 풀었다. 

 

해시맵의 key 값을 x,y값으로 하고 value에는 세포의 정보를 담았다.

초기에 좌상단이 0,0이므로 왼쪽으로 커진다면 마이너스 값이 키값으로 들어가게 되었다.

어차피 키값(인덱스값) 관리만 잘해준다면, 배열처럼 O(1)로 조회할 수 있기 때문에 bfs를 할때도 비효율적일 것은 없다고 생각했다.

 

나중에 사람들이 푼걸 좀 보니 배열을 주로 이용했는데, 배열의 최대 크기를 예상해서 배열을 크게 만들고,

시작을 배열의 중간에서 시작하는 방법을 주로 많이 쓰더라..!!

그래서 이것도 아래 정리해보면서 공부해보려한다.

 

참고로, 해시맵을 돌면서 번식을 하는데, 죽은 세포와 살아있는 세포는 따로 해시맵을 두어서 쓸데없는 시간을 줄이도록 했다.

또, 세포 정보에는 생성된 시간과 생명력을 저장하도록 해, 이를 현재 시간과 비교해서 활성 상태,비활성 상태,번식을 하도록 했다.

두 개 이상이 같은 곳으로 동시에 번식하려고 하는 경우, 생명력 수치가 더 높은 세포를 해시맵에 put했다.(맵은 put할 경우 갱신되기 때문)

 

 

크기가 무한해지는 걸 어떻게할까의 고민을 해결하고보니, 생각보다 쉽게 풀렸다.

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

/**
 * k시간 후 살아있는 줄기세포(비활성 + 활성) 총 개수 구하기
 * <p>
 * 초기 : 비활성 상태(x시간동안) 활성 - x시간동안 살아있은 후 죽음 - 첫1시간동안 네방향으로 동시에 번식(번식된 곳은 비활성) - 이미 줄기세포가 있는곳으론 번식 못함 - 두개이상이 같은곳으로 동시
 * 번식하려고하는 경우 생명력 수치가 높은 줄기세포가 함
 */

class Main {
    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    static class Cell {
        int x, y;
        int health;
        int createTime;
        int state; //0: 비활성, 1: 활성, 2: 죽음

        public Cell(int x, int y, int health, int createTime, int state) {
            this.x = x;
            this.y = y;
            this.health = health;
            this.createTime = createTime;
            this.state = state;
        }
    }

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

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

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            Map<Point, Cell> cells_lived = new HashMap<>();
            Set<Point> cells_dead = new HashSet<>();

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < m; j++) {
                    int health = Integer.parseInt(st.nextToken());
                    if (health == 0) {
                        continue;
                    }
                    cells_lived.put(new Point(i, j), new Cell(i, j, health, 0, 0));
                }
            }

            int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
            for (int time = 1; time <= k; time++) {
                Map<Point, Cell> newCells = new HashMap<>();  //새로 번식하는 세포들
                List<Point> dead = new ArrayList<>();  //새로 죽는 세포들

                for (Entry<Point, Cell> cellEntry : cells_lived.entrySet()) {
                    int x = cellEntry.getKey().x;
                    int y = cellEntry.getKey().y;
                    Cell cell = cellEntry.getValue();

                    if (cell.state == 2) {
                        continue;
                    }

                    if (cell.state == 0 && (cell.createTime + cell.health) == time) {
                        cell.state = 1;  //활성화 상태로 변경
                    } else if (cell.state == 1) {
                        if (cell.createTime + cell.health + 1 == time) {
                            //번식
                            for (int i = 0; i < 4; i++) {
                                int nx = x + dx[i];
                                int ny = y + dy[i];
                                Point next = new Point(nx, ny);

                                if (cells_lived.containsKey(next) || cells_dead.contains(next)) {
                                    continue;
                                }

                                //두개 이상이 같은곳으로 동시 번식하려는 경우, 생명력 수치가 더 높은걸로 갱신
                                if ((newCells.containsKey(next) && newCells.get(next).health < cell.health)
                                        || !newCells.containsKey(next)) {
                                    newCells.put(next, new Cell(nx, ny, cell.health, time, 0));
                                }
                            }
                        }
                        if (cell.createTime + cell.health * 2 == time) {  //죽은 상태로 변경
                            cell.state = 2;
                            dead.add(new Point(x, y));
                        }
                    }

                }

                cells_lived.putAll(newCells);

                for (Point point : dead) {  //살아있는 세포들에서 죽은 세포 제거
                    cells_lived.remove(point);
                }
                cells_dead.addAll(dead);
            }

            sb.append('#').append(tc).append(' ').append(cells_lived.size()).append('\n');
        }
        br.close();
        System.out.print(sb);
    }
}

 

 

 

 

다른 풀이

앞서 말한대로 난 해시맵을 이용해서 풀었지만, 대부분은 배열을 크게 선언해서 사용한걸 봤다.

어차피 배열은 n*m이고 위아래로 최대 K만큼 더 커질 수 있기 때문에 map[n+2*k][m+2*k]으로 선언하면 된다.

 

사실 근데 이거보다 작게 선언해도 된다.

세포 생명력 수치가 1일때 가장 빠르게 번식하는데, 이 세포는 2시간에 한번씩 증식하기 때문에

k시간동안 최대 k/2번 증식한다고 볼 수 있다. 그래서 map[n+k][m+k]로 잡아도 된다.

 

이렇게 배열의 최대 크기?를 예상한 후 생성해서 푸는 방법도 좋은 것 같다.

대부분의 사람들이 이렇게 푼거보니 내가 푼 방법은 신기한 것 같다.

 

 

 

 

느낀점

그래도 사람들이 주로 안 푼 방법으로 푼 것도 뭔가 뿌듯? 했다.

그래도 여러가지 풀이들을 보면서 실력을 키워야겠다 생각이든다.