[구현] 미생물 격리(SWEA 2382, 자바)☆☆

 

문제 

정사각형 구역 안에 K개의 미생물 군집이 있다. 이 구역은 N*N 크기의 동일한 정사각형 셀들로 이루어져 있고, 가장 바깥쪽 가장장리의 셀에는 특수한 약품이 칠해져 있다. 

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

2. 약품이 칠해진 셀에 도착하면 군집 내 미생물 절반이 죽고, 이동방향이 반대로 바뀐다. (미생물 수를 2로 나눈 후, 소숫점 이하를 버림한 값)

 

 

입력

테스트 케이스 개수

한 변의 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K

K줄에 걸쳐 군집의 정보 

 

출력

M시간 후 남아있는 미생물 수의 총 합 

 

 

구현 

1. 미생물 군집의 위치 좌표, 방향, 미생물 수, 위치하는 칸의 번호 를 Cluster 클래스로 만들고, 이들 객체를 리스트에 저장 

2.  Cluster 클래스를 위치번호 순, 존재하는 칸의 번호 순으로 정렬

3. 같은 칸 번호를 가지면, 하나로 병합해주고, 병합된 군집은 삭제(삭제 시, 인덱스 주의!!)

 

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

public class Solution {

	static int N,M,K;
	static ArrayList<Cluster> arr;
	static int[] dx= {-1, 0, 1, 0};
	static int[] dy= { 0, -1, 0, 1};
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int T=Integer.parseInt(br.readLine());
		
		for(int t_c=1;t_c<=T;t_c++) {
			
			StringTokenizer st=new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			M=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			
			arr=new ArrayList<>();
			
			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 cnt=Integer.parseInt(st.nextToken());
				int direction=Integer.parseInt(st.nextToken());
				
				//방향 인덱스 0: 위, 1: 왼, 2: 아래, 3: 오른 으로 설정
				if(direction==3) direction=1;
				else if(direction==1) direction=0;
				else if(direction==4) direction=3;
				
				arr.add(new Cluster(x,y,cnt,direction,x*N+y));
				
			}
			
			int i=0;
			while(i<M) { //M시간 동안 이동 
	
				for(int j=0;j<arr.size();j++) {
					
					Cluster c1=arr.get(j);
					
					int x=c1.x+dx[c1.direction];
					int y=c1.y+dy[c1.direction];
					
					c1.x=x;
					c1.y=y;
					
					c1.num=x*N+y; 
					
					if(x==0 || x==N-1 || y==0 || y==N-1) {
						c1.cnt/=2;
						if(c1.cnt==0) { //미생물의 개수가 0이 되는 경우 
							arr.remove(j);
							j--;
						}
						else { //방향은 반대로 
							c1.direction=(c1.direction+2)%4;
						}
						
					}
				}
				
				Collections.sort(arr); //arr 내 미생물 군집들을 정렬
				
				for(int j=0;j<arr.size()-1;j++) {
				
					Cluster now=arr.get(j);
					Cluster next=arr.get(j+1);
					
					if(now.num==next.num) {
						next.cnt+=now.cnt;
						arr.remove(j);
						j--;
					}	
				}
				i++;
				
			}
			
			int sum=0;
			for(int j=0;j<arr.size();j++) {
				sum+=arr.get(j).cnt;
			}
				System.out.println("#"+t_c+" "+sum);
		}	
		
	}
	
	static class Cluster implements Comparable<Cluster>{
		
		int x; 
		int y;
		int cnt;
		int direction;
		int num;
		
		public Cluster(int x, int y, int cnt, int direction, int num) {
			super();
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.direction = direction;
			this.num=num;
		}

		@Override
		public int compareTo(Cluster o) { 
			if(this.num==o.num) {
				return this.cnt-o.cnt;
			}
			return this.num-o.num;
		}

	}
}