SWEA_미생물격리_2382

1. 과정

- 자료구조는 한 셀에 여러 군집이 올 수 있으니 리스트 타입의 2차원 배열을 선택했다.

- 한 군집은 클래스로 만들어 위치와, 미생물 수, 방향을 상태로 가졌다.

- 총 M번 동안 군집들이 한칸씩 이동하므로 Queue에 넣고, 모두 한칸씩 움직인 후 합쳐지거나 사라진 군집은 다시 넣지 않았다.

 

 

2. 구현

언어 : JAVA

메모리 : 112,656 kb

실행시간 : 772 ms

import java.io.*;
import java.util.*;

public class SWEA_미생물격리_2382 {
	static int N, M, K, answer;
	static int[] dr = {0, -1, 1, 0, 0};
	static int[] dc = {0, 0, 0, -1, 1};
	static ArrayList<Group>[][] map;
	static Queue<Group> q = new LinkedList<>();
	
	static class Group{
		int r, c, num, dir;

		public Group(int r, int c, int num, int dir) {
			this.r = r;
			this.c = c;
			this.num = num;
			this.dir = dir;
		}
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int testCase = 1; testCase<=T; ++testCase) {
			answer = 0;
			q.clear();
			
			String[] s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			M = Integer.parseInt(s[1]);
			K = Integer.parseInt(s[2]);
			map = new ArrayList[N][N];
			
			for(int i=0; i<N; ++i)
				for(int j=0; j<N; ++j)
					map[i][j] = new ArrayList<>();
			
			for(int i=0; i<K; ++i) {
				s = br.readLine().split(" ");
				int r = Integer.parseInt(s[0]);
				int c = Integer.parseInt(s[1]);
				int num = Integer.parseInt(s[2]);
				int dir = Integer.parseInt(s[3]);
				Group group = new Group(r, c, num, dir);
				q.add(group);
			}
			
			// M번 반복
			for(int i=0; i<M; ++i) {
				// 모든 군집을 이동시킴
				while(!q.isEmpty()) {
					Group g = q.poll();
					int r = g.r;
					int c = g.c;
					int num = g.num;
					int dir = g.dir;
					int tr = r+dr[dir];
					int tc = c+dc[dir];
					if(tr==0||tc==0||tr==N-1||tc==N-1) {
						num /= 2;
						if(num==0) continue;
						if(dir==1)
							dir = 2;
						else if(dir==2)
							dir = 1;
						else if(dir==3)
							dir = 4;
						else
							dir = 3;
					}
					// 이동된 군집은 map에 저장
					map[tr][tc].add(new Group(tr, tc, num, dir));					
				}				
				
				// 모든 map을 돌며 q에 다시 넣을 때, 여러 군집이 있는 경우 가장 많은 미생물의 군집에 합쳐줌
				for(int j=0; j<N; ++j) {
					for(int k=0; k<N; ++k) {
						if(map[j][k].isEmpty()) continue;
						if(map[j][k].size()==1)
							q.add(map[j][k].get(0));
						else {
							int total = 0;
							int max = 0;
							int maxr=0, maxc=0, maxdir=0;
							for(int x=0; x<map[j][k].size(); ++x) {
								Group g = map[j][k].get(x);
								total += g.num;
								if(max<g.num) {
									max = g.num;
									maxr = g.r;
									maxc = g.c;
									maxdir = g.dir;
								}
							}
							q.add(new Group(maxr, maxc, total, maxdir));
						}
						map[j][k].clear();
					}
				}
				
				// M번 반복 했다면 남은 군집의 총 미생물 수를 구함
				if(i==M-1) {
					while(!q.isEmpty()) {
						Group g = q.poll();
						answer += g.num;
					}
					break;
				}						
			}
			
			System.out.println("#"+testCase+" "+answer);
			
		}
		
	}

}