[SWEA 2382] 미생물 격리

[문제]

정사각형 구역 안에 K개의 미생물 군집이 있다.

이 구역은 가로 N개, 세로 N개, 총 N * N 개의 동일한 크기의 정사각형 셀들로 이루어져 있다.

미생물들이 구역을 벗어나는걸 방지하기 위해, 가장 바깥쪽 가장자리 부분에 위치한 셀들에는 특수한 약품이 칠해져 있다.

[Fig. 1]은 9개의 군집이 한 변이 7개의 셀로 이루어진 구역에 배치되어 있는 예이다.

가장자리의 빨간 셀은 약품이 칠해져 있는 셀이다.

① 최초 각 미생물 군집의 위치와 군집 내 미생물의 수, 이동 방향이 주어진다. 약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.

② 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.

③ 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다.
미생물 수가 홀수인 경우 반으로 나누어 떨어지지 않으므로, 다음과 같이 정의한다.
살아남은 미생물 수 = 원래 미생물 수를 2로 나눈 후 소수점 이하를 버림 한 값
따라서 군집에 미생물이 한 마리 있는 경우 살아남은 미생물 수가 0이 되기 때문에, 군집이 사라지게 된다,

④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.
합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.

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

---

[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 5초

2. 구역의 모양은 정사각형으로 주어지며, 한 변의 셀의 개수 N은 5이상 100이하의 정수이다. (5 ≤ N ≤ 100)

3. 최초 배치되어 있는 미생물 군집의 개수 K는 5이상 1,000이하의 정수이다. (5 ≤ K ≤ 1,000)

4. 격리 시간 M은 1이상 1,000이하의 정수이다. (1 ≤ M ≤ 1,000)

5. 최초 약품이 칠해진 가장자리 부분 셀에는 미생물 군집이 배치되어 있지 않다.

6. 최초에 둘 이상의 군집이 동일한 셀에 배치되는 경우는 없다.

7. 각 군집 내 미생물 수는 1 이상 10,000 이하의 정수이다.

8. 군집의 이동방향은 상하좌우 4방향 중 한 방향을 가진다. (상: 1, 하: 2, 좌: 3, 우: 4)

9. 주어진 입력으로 진행하였을 때, 동일한 셀에 같은 미생물 수를 갖는 두 군집이 모이는 경우는 발생하지 않는다.

10. 각 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 주어진다. 각 위치는 0번부터 시작한다.

[입력]

첫 줄에는 총 테스트 케이스의 개수 T가 주어진다.

그 다음 줄부터 T개의 테스트 케이스가 차례대로 주어진다.

각 테스트 케이스의 첫째 줄에는 구역의 한 변에 있는 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K가 순서대로 주어지며, 다음 K줄에 걸쳐서 미생물 군집 K개의 정보가 주어진다.

미생물 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 4개의 정수가 주어진다.

[출력]

테스트 케이스의 개수 만큼 T개의 줄에 각 테스트 케이스에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고, 공백을 하나 둔 후 정답을 출력한다. (x는 테스트 케이스의 번호이며, 1번부터 시작한다.)

출력해야 할 정답은 M시간 후 남아 있는 미생물 수의 총 합이다.

[풀이]

문제에 제시되어 있는 조건들을 하나씩 코드로 구현해보면 풀 수 있는 문제다. (1) 맨 처음 미생물 군집의 정보에 대한 객체(클래스)를 생성한다. (2) 미생물 군집이 이동 좌표 값을 초기화한다. (3) 미생물 군집의 수만큼 각각의 미생물 군집의 정보를 입력받는다. (4) M시간 후 남아 있는 미생물 군집 정보를 파악하기 위해 count <=M 동안 반복한다. (5) 각 미생물 군집마다 이동시켜 (6) 이동을 완료한 미생물 군집이 약품이 칠해져 있는 곳이라면 (7) 미생물 군집 수를 절반으로 줄인다. 약품이 칠해진 곳에 도달하면 (8) 방향을 정반대 방향으로 전환시킨다. 약품 칠해져 있는 곳의 작업이 끝난 후 (9) 해당 미생물의 수가 남아있는 것이 없다면 제거하고, (10) 한 좌표에 군집이 2개 이상인 곳을 구별해야 합치는 작업을 해야하기 때문에 해당 그룹의 수를 1씩 증가시켜준다. 미생물 이동을 완료한 후 (11) 미생물의 크기가 0인 미생물들을 모두 제거한다.
(12) 모든 좌표를 탐색하여 해당 좌표의 군집이 2개이상인 군집을 합친다. (13) 다음 시뮬레이션 때 이동과 합치는 작업을 완료한 후 다시 이동시켜야하므로 그룹 배열을 초기화 시킨다. (14) M시간 후 result변수에 남아있는 미생물들의 총 크기를 더해준다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Solution {
	// (1) 
	static class Microbe{
		int x, y, dir;
		int size;

		public Microbe(int x, int y, int size, int dir) {
			this.x = x;
			this.y = y;
			this.size = size;
			this.dir = dir;
		}
	}
	
	static int N, M, K;	//가로세로, 제한시간, 군집 수
	static int result;
	static int[][] map;
	static int[][] group;
	static ArrayList<Microbe> bio;	//군집 배열
	// (2) 상:1, 하:2, 좌:3, 우:4 
	static int[] dx = {0, -1, 1, 0, 0};
	static int[] dy = {0, 0, 0, -1, 1};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=1; tc<=T; tc++) {
        	st = new StringTokenizer(br.readLine());
        	
        	N = Integer.parseInt(st.nextToken());
        	M = Integer.parseInt(st.nextToken());
        	K = Integer.parseInt(st.nextToken());
        	
        	map = new int[N][N];
        	group = new int[N][N];
        	bio = new ArrayList<>();
        	int count = 1;
        	result = 0;
        	
            // (3)
        	for(int i=0; i<K; i++) {
        		st = new StringTokenizer(br.readLine());
        		
        		int x = Integer.parseInt(st.nextToken());
        		int y = Integer.parseInt(st.nextToken());
        		int size = Integer.parseInt(st.nextToken());
        		int d = Integer.parseInt(st.nextToken());
        		
        		bio.add(new Microbe(x, y, size, d));
        	}	//입력완료
        	
            // (4)
        	while(count <= M) {	
            	// (5) 
        		for(int i=0; i<bio.size(); i++) {
        			int nx = bio.get(i).x + dx[bio.get(i).dir];	//이동
        			int ny = bio.get(i).y + dy[bio.get(i).dir];
        			
        			bio.get(i).x = nx;	//좌표 이동
        			bio.get(i).y = ny;
        			
        			// (6) 군집이 약품이 칠해져있는 위치일 경우
        			if(nx == 0 || ny == 0 || nx == N-1 || ny == N-1) {
        				
        				// (7) 미생물 수 절반으로 줄이기
        				bio.get(i).size /= 2;
        				
        				
        				
        				// (8) 방향 전환
        				if(bio.get(i).dir == 1) bio.get(i).dir = 2;
        				else if (bio.get(i).dir == 2) bio.get(i).dir = 1;
        				else if (bio.get(i).dir == 3) bio.get(i).dir = 4;
        				else if (bio.get(i).dir == 4) bio.get(i).dir = 3;
        				
        				
        			}
        			
//        			if(bio.get(i).size == 0) bio.remove(i);	// (9) 미생물 수가 0이면 제거
        			
        			group[nx][ny]++; // (10)한 셀에 군집이 두개 이상인지 판별하기 위함
        		}
        		
                // (11) 
        		bio.removeIf(v->v.size == 0);
        		
        		// (12) 
        		for(int i=0; i<N; i++) {
        			for(int j=0; j<N; j++) {
        				if(group[i][j] >= 2) {	//군집이 한 셀에 2개 이상인 경우
        					sum(i, j);			//군집 합치기
        				}
        			}
        		}
        		
                // (13)
        		group = new int[N][N];			//군집 수 배열 초기화
        		count++;						//while문 조건 빠져나오기 위한 count++
        	}
        	
            // (14)
        	for(int i=0; i<bio.size(); i++) {
        		result += bio.get(i).size;
        	}
        	
        	System.out.println("#"+tc+" "+result);
        	
        }
        
	}

	
	private static void sum(int r, int c) {
		int tmp_size = 0;	//미생물 수
		int num = 0;		//겹치는 군집의 미생물 수의 총 합
		int di = 0;			//겹치는 군집의 방향
		
		for(int b=0; b<bio.size(); b++) {
			if(bio.get(b).x == r && bio.get(b).y == c) {
				num += bio.get(b).size;
				
				if(tmp_size < bio.get(b).size) {
					tmp_size = bio.get(b).size;
					di = bio.get(b).dir;
				}
			}
		}
		
		
		bio.removeIf(v->v.x == r && v.y == c);
		
		bio.add(new Microbe(r, c, num, di));
		
	}

}