문제분석

1. 최초 각 미생물 군집의 위치와 군집 내 미생물의 수, 이동 방향이 주어진다. 약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.
2. 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.
3. 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다. 
   미생물 수가 홀수인 경우 반으로 나누어 떨어지지 않으므로, 다음과 같이 정의한다.
   살아남은 미생물 수 = 원래 미생물 수를 2로 나눈 후 소수점 이하를 버림 한 값
   따라서 군집에 미생물이 한 마리 있는 경우 살아남은 미생물 수가 0이 되기 때문에, 군집이 사라지게 된다,  
   4. 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 
   합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다. 
   합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.

M 시간 동안 이 미생물 군집들을 격리하였다. M시간 후 남아 있는 미생물 수의 총합을 구하여라.

문제에서 요구하는 과정을 쭉 따라가면 된다. 다만 주의해야 할 부분이 하나있다.
미생물이 합쳐지는 부분이다. 미생물이 합쳐질때, 최대 4개의 방향에서 합쳐지는 경우가 있다. 이러한 경우가 있기 때문에 미생물의 크기별 정렬이 필요하다. 하지만, 이러한 정렬은 위치가 같을때만 유효하기 때문에 Comparable 클래스를 이용하여, 미생물 정렬 기준을 따로 잡아주어야 한다.

문제에서 요구하는 사항을 따라가며 문제를 풀어보도록하자

문제 풀이

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  
  
/**  
 * @author onyoo  
 * @performance  
 * @category  
 * @note  
 * 군집의 이동경로를 파악하고 다음과 같은 조건을 처리해야한다  
 * 1.군집은 1시간마다 이동방향으로 이동한다  
 * 2.약품에 칠해진 셀에 도착하면 군집 내 절반이 죽고, 이동방향이 반대로 바뀐다. 살아남은 미생물 수 = 반으로 나눈 후 소수점 이하를 버림 한 값  
 * 소수점이 된 군집은 1이하이기 때문에 군집이 사라진다.  
 * 3.두개이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 이동방향은 미생물 수가 많은 군집의 이동방향을 따른다.  
 * 1시간마다 미생물의 이동경로를 직접 잡아준 뒤, 겹치는 경우 예외처리를 따로 해주면 된다.  
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl  
 * @since 2023-10-05  
 **/public class 미생물격리 {  
    static class Point{  
        int x,y;  
  
        public Point(int x, int y) {  
            this.x = x;  
            this.y = y;  
        }  
  
    }  // 미생물의 위치 좌표를 나타내는 Point 클래스
  
    static class Microbe implements Comparable<Microbe>{  
        Point dir;  
        int m,s;  
        //미생물 방향,크기  
        int idx; // 미생물 번호  
  
        public Microbe(Point dir, int m, int s) {  
            this.dir = dir;  
            this.m = m;  
            this.s = s;  
            this.idx = dir.x * N + dir.y;  
        }  
  
        public void move(){  
            dir.x += dx[m];  
            dir.y += dy[m];  
            idx = dir.x * N + dir.y;  
  
            if(dir.x == 0 || dir.y == 0 || dir.x == N - 1 || dir.y == N - 1) {  
                s /= 2;  
                if(m % 2 == 0)  m++;  
                else m--;  
            } // 부딪힐 경우 반감되고 방향이 바뀐다  
        }
        // 미생물의 움직임을 구현한 메서드 
        // 미생물이 사라지는 경우는,리스트에서 제거하는 로직이 필요하기 때문에 따로 구현함
  
        @Override  
        public int compareTo(Microbe o) {  
            if(idx == o.idx) return -(s-o.s);  // 위치가 같을 경우 사이즈가 큰 순으로 정렬함
            return idx - o.idx;  // 이외의 경우에는 위치 순서대로 정렬함 
        }  
        // 미생물 이동  
    }  
  
    static int T,N,M,K;  
    static ArrayList<Microbe> list;  
    static int[] dx = {-1,1,0,0};  
    static int[] dy = {0,0,-1,1};  
    static int answer;  
    // T 테스트케이스 개수  
    // N 셀의 크기  
    // M 격리시간  
    // K 미생물 군집의 개수  
    // 격리시간동안 남아있는 미생물 수의 총합을 구하자  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st;  
  
        T = Integer.parseInt(br.readLine());  
  
        for(int t = 1; t < T + 1 ; t++){  
            st = new StringTokenizer(br.readLine()," ");  
            N = Integer.parseInt(st.nextToken());  
            M = Integer.parseInt(st.nextToken());  
            K = Integer.parseInt(st.nextToken());  
  
            list = new ArrayList<Microbe>();  
  
            answer = 0;  
  
            for(int k = 0; k < K; k++){  
                st = new StringTokenizer(br.readLine()," ");  
                int x = Integer.parseInt(st.nextToken());  
                int y = Integer.parseInt(st.nextToken());  
                int count = Integer.parseInt(st.nextToken());  
                int dir = Integer.parseInt(st.nextToken()) - 1;  
  
                list.add(new Microbe(new Point(x,y),dir,count));  
  
            }  
  
            for(int time = 0; time < M; time++){  
                // 시뮬레이션 시작  
  
                for(int i=0;i<list.size();i++) {  
                    Microbe microbe = list.get(i);  
                    microbe.move();  
                    if(microbe.s == 0) {  
                        list.remove(i);  
                        i--;  
                    }  
                }  
  
                Collections.sort(list);  
  
                for(int i=0;i<list.size()-1;i++){  
                    Microbe ex = list.get(i);  
                    Microbe curr = list.get(i+1);  
  
                    if(ex.idx == curr.idx) {  
                        ex.s += curr.s;  
                        list.remove(i+1); // 삭제한다  
                        i--;  
                    }  
                }  
            }  
  
            for(Microbe m : list) answer += m.s;  
  
            System.out.printf("#%d %d \n",t,answer);  
        }  
    }  
}