[SW Expert] 2382. [모의 SW 역량테스트] 미생물 격리

생각

미생물이 담긴 N 크기의 배열과 안에 들어있는 미생물 군집들이 주어진다.
군집은 상 하 좌 우중 한 방향으로만 움직이며, N 배열의 가장 바깥줄(경계면)에 도달하면
현 생명력이 반절로 줄어들고 움직이는 방향은 반대 방향이 된다.(소수 단위는 절삭한다)
군집들은 1초에 한 칸씩만 움직이며 M 초동안 움직인다.
군집들이 한 칸에서 만날경우 미생물 수가 합쳐지며 방향은 가장 큰 군집이 가던 방향으로 결정된다.
군집이 서로 지나칠 경우는 만나는 경우가 아니다.
이 때, M 초후에 남아있는 미생물의 수를 구하시오.

이전 생각

이전에 풀어보았던 문제인 (모의 SW 역량테스트] 원자 소멸 시뮬레이션) 와 상위호환? 하위호환? 되는 비슷한 문제이다. 요 문제의 경우는 무조건 부딪히는 원자와 다르게 서로 마주보고 있으면 지나간다는 점과 끝 줄에 도착하면 생명력이 반 절이 되면서 방향이 반대가 되는게 다르다.

다음 생각

우선 원자 소멸 시뮬레이션 문제를 생각해서 비슷하게 풀어보려다가 속 내용은 다른 문제인 것을 깨달았다. 바로 군집들이 만날 경우 사라지는 것이 아니라 합쳐지면서 가장 큰 군집의 방향으로 계속 나아가야 하기 때문이다.

다다음 생각

따라서 어떠한 칸에서 만났을 때, 현 군집과 비교하기 위해서 이전 군집의 생물수, 방향을 알고 있어야 하고, 계속 더해주기 위해서 더한 값과 2개가 아니라 최대 4개의 군집이 만날 수 있으므로, 가장 큰 생물수를 가지고 있는 max 값도 있어야 했다.

다다다음 생각

처음에는 바로바로 비교를 위해서 2차 배열의 타입으로 inner class로 만든 객체를 사용했는데 테스트 케이스를 돌리는데도 메모리 초과가 났다.

▶ Queue의 타입말고, 2차 배열의 타입을 레퍼런스 타입으로 지정하는 일이 없도록 해야겠다. 항상 프리미티브로 사용하는게 좋겠다!!!

다다다다음 생각

2차 배열을 레퍼런스 타입으로 지정할 수 없어져서 각각 역활(미생물 수, 최대 값, 방향)을 하는 3차 배열 프리미티브 타입(int)를 3개를 만들어 주었다. 그리고 충돌 했을 경우를 알기 위해서 방문 개수를 표시하는 visited 3차 배열도 하나 만들어 주었다.

▶ 3차 배열로 만들어준 이유는 [x좌표][y좌표][시간] 으로 시간을 통해서 겹치는걸 구분하기 위해서 였다. 위치만 따졌을 때 겹치는 케이스는 아래 그림에서 빨간색이 먼저 진행할 경우 queue의 특성으로 인해서 빨간색이 도달했을 때, 해당 위치값이 2 이상이 되어있는 경우이다.

▶ 테스트 케이스는 잘 통과했으나 제출시 다음과 같이 나왔다.

▶ 제출 내역을 확인해보니 제한된 메모리 사용량을 넘었다.

다다다다다음 생각

우선 시간대 별로 충돌을 점검하기 때문에 visited 배열만 시간을 체크하기 위해서 3차 배열로 남겨두고, 나머지 배열들을 2차로 바꾸어 주었더니 통과하였다.

방안

1) 메모리 문제를 얕봐서는 안될 것 같다. 

▶ 배열은 프리미티브 타입을 쓰도록 생각하고, 2차를 초과하는 배열은 최대 2개 정도 까지만 해준다면 개수가 1000개 일 때 제한 사항을 벗어나는 일은 없을 것 같다.

2) 방문 표시를 위해서 배열을 사용하니 좀 더 편한것 같다. 나중에 원소 소멸 시뮬레이션을 다시 풀어볼 때, 배열로 풀어봐야겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution{
    static int n,m,k;
    static int[][][] visited;
    static int[][] arrM,arrN,arrD;
    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());
        visited = new int[100][100][1001];
        arrN = new int[100][100];
        arrD = new int[100][100];
        arrM = new int[100][100];
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            // 미생물 받기
            Pair[] live = new Pair[k];
            for(int j=0;j<k;j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int n = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                live[j] = new Pair(x, y, n, d,0);
            }
            sb.append("#"+i+" "+solve(live)+"\n");
        }
        System.out.print(sb);
    }
    
    private static int solve(Pair[] live) {
        Queue<Pair> queue = new LinkedList<>();
        // queue 넣어주기 & 배열에 미생물 넣기
        for(int i=0;i<k;i++) {
            queue.add(live[i]);
            visited[live[i].x][live[i].y][0]++;
        }
        int result = 0;
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            // 현 좌표가 1보다 크다면 부딪혀있는것. & 이동안한것 거르기.
            if(visited[t.x][t.y][t.time]>1) {
                if(t.n>arrM[t.x][t.y]) {
                    arrN[t.x][t.y] += t.n;
                    arrD[t.x][t.y] = t.d;
                    arrM[t.x][t.y] = t.n;
                }else arrN[t.x][t.y] += t.n;
                visited[t.x][t.y][t.time]--;
                continue;
            }else {
                if(t.n<arrM[t.x][t.y]) {
                    t.d = arrD[t.x][t.y];
                    t.n += arrN[t.x][t.y];
                }else {
                    t.n += arrN[t.x][t.y];
                }
                init(t.x,t.y,t.time);
            }
            if(t.time==m) {
                result += t.n;
                // 다음 예제 사용을 위한 초기화
                init(t.x, t.y, t.time);
                continue;
            }
            int tx = t.x, ty = t.y;
            switch(t.d) {
            case 1: tx-=1; break; // 상
            case 2: tx+=1; break; // 하
            case 3: ty-=1; break; // 좌
            case 4: ty+=1; break; // 우
            }
            // 경계 면이라면 방향을 바꿔준 후, 생물 수 /2
            if(tx==0 || ty==0 || tx==n-1 || ty==n-1) {
                // 방향 바꿔주기
                switch(t.d) {
                case 1: t.d=2; break;
                case 2: t.d=1; break;
                case 3: t.d=4; break;
                case 4: t.d=3; break;
                }
                // 생물 수 /2
                t.n /=2;
                if(t.n==0) {
                    visited[t.x][t.y][t.time]--;
                    continue;
                }
            }
            // 방향과 미생물 수를 바꿔주었으니 다음 칸으로 이동.
            init(t.x,t.y,t.time);
            visited[tx][ty][t.time+1]++;
            queue.add(new Pair(tx, ty, t.n, t.d, t.time+1));
        }
        return result;
    }
    
    private static void init(int x,int y,int time) {
        arrN[x][y] = 0;
        arrD[x][y] = 0;
        arrM[x][y] = 0;
        visited[x][y][time] = 0;
    }
    
    static class Pair{
        private int x,y,n,d,time;
        public Pair(int x,int y,int n,int d,int time) {
            this.x=x;
            this.y=y;
            this.n=n;
            this.d=d;
            this.time=time;
        }
    }
}