[JAVA] [SWEA] 2382. 미생물 격리

이 문제는 무려 5초를 주었다는 점과 N의 수가 작아 N*N을 하더라도 10000인 점 미생물의 수가 1000개 이하라는 점이 무조건 시뮬레이션이라는 생각이 들어 쉽게 풀게 되었다.

 

내가 사용한 변수들은 int[][] maxMap, int[][] dirMap, int[][] sumMap 이다 이름만 봐도 어떤 용도인지 알겠으나 나중에 더 자세히 설명하겠다.

 

1. m일 동안 진행하기 때문에 0~m-1까지 for문 돌기

2. 미생물이 합쳐지기도 죽기도 하기때문에 list가 아닌 Queue 사용 하였는데 하루동안 한칸만 움직여야 하기때문에 Q의 사이즈를 이용하여 그만큼만 for문을 돌아주었다.

3. 문제에 나와있듯이 한칸 움직인 후 배열의 가장 바깥쪽 칸들에 가면 크기를 반으로 줄이고 방향을 반대로 바꿔주었다.

4. 이때 Q에서 빼낸 미생물들은 maxMap, dirMap, sumMap에 써주는데 maxMap에 값이 있을 경우와 없을 경우를 나누어 생각을 하였다. ( 하지만 더 효율적으로 합칠 수도 있을 것 같다. ) 

5. maxMap에 값이 있는 경우 지금 값과 비교하여 더 큰값을 넣어주고 ( 2개가 아니라 3개 이상의 미생물이 합칠 경우 방향을 정해줄 때 사용하기 위해 ) 들어간 미생물의 수를 sumMap에 더해주고 dirMap에 maxMap과의 비교 관계에 따라 업데이트 해주었다. 

6. 이 때 HashMap에 좌표값을 I * N + J 로 나타내어 넣어주었는데 이는 대소관계 비교에도 쉽게 equal을 진행하는데 있어 객체보다 쉬울 것이라 생각이 들어 더 편하게 쓰기위해 이런 식으로 넣어두었다.

( 사실 좌표만 넣고 어차피 값은 Map에 있는 것들을 참고 하기 때문에 좌표만 넣는 것이라면 int[] 도 상관없다 본인이 편한 것으로 하기 바란다. )

7. HashMap에서 값을 하나씩 빼내어 다시 큐에 넣어주면 된다. ( 물론 hashSet을 클리어 해준 다는 점을 잊지 말자 ! )

8. 자 약속한 m일이 지났을때 Q에 있는 값들을 더하여 출력해주면 된다.

 

정말 자세히 썼으나 더 필요하거나 궁금한 점은 댓글을 달아주시면 감사합니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	static class micro{
		int i, j, cnt, dir;
		public micro(int i, int j, int cnt, int dir) {
			this.i = i;
			this.j = j;
			this.cnt = cnt;
			this.dir = dir;
		}
	}

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] str = null;
		int n = 0;
		int m = 0;
		int k = 0;
		Queue<micro> q = new LinkedList<micro>();
		int[][] maxMap = null;
		int[][] dirMap = null;
		int[][] sumMap = null;
		int qSize = 0;
		int di = 0;
		int dj = 0;
		int cnt = 0;
		int dir = 0;
		int result = 0;
		micro mic = null;
		for(int t=1; t<=T; ++t) {
			q.clear();
			result = 0;
			str = br.readLine().split(" ");
			n = Integer.parseInt(str[0]);
			m = Integer.parseInt(str[1]);
			k = Integer.parseInt(str[2]);
			maxMap = new int[n][n];
			dirMap = new int[n][n];
			sumMap = new int[n][n];
			for(int i=0; i<k; ++i) {
				str = br.readLine().split(" ");
				di = Integer.parseInt(str[0]);
				dj = Integer.parseInt(str[1]);
				cnt = Integer.parseInt(str[2]);
				dir = Integer.parseInt(str[3]);
				q.offer(new micro(di, dj, cnt, dir));
			}
			for(int i=0; i<m; ++i) {
				qSize = q.size();
				for(int j=0; j<qSize; ++j) {
					mic = q.poll();
					// 상 1 , 하 2 , 좌 3, 우 4
					di = mic.i;
					dj = mic.j;
					cnt = mic.cnt;
					dir = mic.dir;
					if(dir == 1) {
						di--;
					}else if(dir == 2) {
						di++;
					}else if(dir == 3) {
						dj--;
					}else {
						dj++;
					}
					if(dj == 0 || dj == n-1 || di == 0 || di == n-1) {
						if(dir == 1 || dir == 3) {
							dir++;
						}else {
							dir--;
						}
						cnt /= 2;
					}
					if(maxMap[di][dj] != 0) {
						if(maxMap[di][dj] < cnt) {
							maxMap[di][dj] = cnt;
							dirMap[di][dj] = dir;
						}
						sumMap[di][dj] += cnt;
					}else {
						maxMap[di][dj] = cnt;
						dirMap[di][dj] = dir;
						sumMap[di][dj] = cnt;
					}
				}
				
				for(int j=0; j<n; ++j) {
					for(int l=0; l<n; ++l) {
						if(maxMap[j][l] > 0) {							
							
							q.offer(new micro(j, l, sumMap[j][l], dirMap[j][l]));
							if(i != m-1) {
								sumMap[j][l] = 0;
								dirMap[j][l] = 0;
								maxMap[j][l] = 0;
							}
						}
					}
				}
			}
			while(!q.isEmpty()) {
				mic = q.poll();
				result += mic.cnt;
			}
			bw.write("#"+t+" "+result+"\n");
		}
		bw.close();
		br.close();
	}
}