2382. [모의 SW 역량테스트] 미생물 격리

시뮬레이션 문제입니다. 제가 문제를 풀면서 막혔던 부분은 두 개 이상의 군집이 한 셀에 모이는 경우에 군집들이 합쳐지게 되는데, 이동 방향을 군집들 중 미생물 수가 가장 많은 군집을 따라가야 한다는 것이었습니다.

저는 처음 생각했을 때 미생물들을 한 칸씩 움직이면서 겹치면 더 많은 미생물 수를 가진 군집의 이동방향으로 그 때 마다 바꿨습니다. 하지만 이렇게 되면 생기는 문제가 한셀에 미생물 수가 각각 30 -> 50 -> 70 를 가지고 있는 군집들이 순서대로 겹친다고 가정하면 처음에 30과 50을 더해서 미생물 수가 80이고, 50인 방향을 따라가는데 세 번째에서 70 을 가지고 있는 군집이 겹치게 되면 앞에서 더해진 미생물 수 80을 가지고 있고, 70이 더 작기 때문에 150으로 합쳐지면서 방향은 결국 50 의 군집을 따라가게 됩니다. 하지만 문제에서 요구하는 것은 30 -> 50 -> 70 순서로 한 셀에 겹쳤을 때에는 미생물 수 70을 가지고 있는 군집의 방향을 따라가야 합니다.

이 점을 해결하기 위해서 모든 살아있는 미생물 수를 검사하면서 같은 좌표에 있는 군집들의 미생물 수를 더하지만, 처음 가지고 있었던 각각 고유의 미생물 수의 최대값을 가지고 있는 군집의 번호와 방향을 기억하면서 초기화 해주었습니다.

[ 문제 풀이 ]

1. micro 라는 미생물 군집을 저장할 class 배열을 만듭니다. 그래서 1 부터 시작해서 주어진 군집들에게 차례대로 고유한 번호를 가지고 연산하게 했습니다. 군집의 수가 0이 돼서 사용하지 않는 alive를 false 로 표시해서 연산을 안하게 했습니다. 2차원 배열에서 계속 움직이는 시뮬레이션 문제들은 직접 2차원 배열에 표시하면서 하는 방식이 아닌 이런 방법객체들을 관리 해야 시간을 줄여서 시간초과를 피할 수 있는 것 같습니다.

2. micro 에 저장되어 있는 군집들을 주어진 방향으로 한 칸씩 움직이는데, null 로 표시된 군집들은 사용하지 않으므로 넘어갑니다.

3. 이제 군집들을 다 움직였으면 약품이 칠해진 곳으로 움직였는지 판단합니다. 약품이 칠해진 곳에서는 절대 군집들이 두개 이상 모일 수 없기 때문에 겹치는지 확인 할 필요가 없고, 미생물 수만 반으로 줄이고 0이면 alive 를 false 로 표시합니다.

4. 약품이 칠해지지 않은 곳으로 움직인 군집들은 이제 겹치는지 확인해 봐야하는데 자신을 제외한 모든 군집들을 한번 더 확인하면서 미생물 수를 비교하고, 미생물 수가 적으면 그 군집을 죽입니다. 하지만 다른 좌표의 미생물 수가 많으면 sum 에 미생물 수를 더하고 max 에 고유의 미생물 수를 저장해서 그 군집의 방향을 따라가야 합니다.

---

import java.util.ArrayList;
import java.util.Scanner;

// 미생물 격리

public class Solution {

	static int N, M, K, result;
	// dir[1]:상, [2]하, [3]좌, [4]우
	static int[][] map, dir = {{0,0},{-1,0},{1,0},{0,-1},{0,1}};
	static int[] change_dir = {0, 2, 1, 4, 3}; 
	static Pair[] micro;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int tc=1; tc<=T; tc++) {
			result = 0;
			N = sc.nextInt(); // 셀의 개수 
			M = sc.nextInt(); // 격리 시간
			K = sc.nextInt(); // 미생물 군집의 개수 
			micro = new Pair[K+1];
			
			// d -> 1 2 3 4  상 하 좌 우
			for(int i=1; i<=K; i++) {
				int r = sc.nextInt();
				int c = sc.nextInt();
				int n = sc.nextInt();
				int dir = sc.nextInt();
				micro[i] = new Pair(r, c, n, dir, true);
			}
			
			// M시간 돌리기
			for(int minute=0; minute<M; minute++) {
				
				// 일단 한칸씩 움직이기
				for(int i=1; i<=micro.length-1; i++) {
					Pair p = micro[i];
					if(!p.alive) continue;
					int nx = p.x + dir[p.d][0];
					int ny = p.y + dir[p.d][1];
					micro[i] = new Pair(nx, ny, p.n, p.d, p.alive);
				}
				
				// 움직여진 군집들
				for(int i=1; i<=micro.length-1; i++) {
					Pair p = micro[i];
					
					if(!p.alive) continue;
					
					// 약품이 칠해진 부분으로 움직인 상태일 때
					if(isOutside(p.x, p.y)) {
						micro[i].n /= 2;
						if(micro[i].n == 0) micro[i].alive = false;
						micro[i].d = change_dir[p.d];
						
					} else {	// 약품이 안칠해진 곳이면

						
						// 같은 좌표에 있을시 가장 큰 미생물의 수와 더해진 미생물의 수값을 구하기 위한 변수 
						int max = p.n;
						int sum = p.n;
						int idx = i;

						for(int j=i+1; j<=micro.length-1; j++) {
							if(!micro[j].alive) continue;
							// 현재 좌표와 같은 좌표를 찾아서
							if(micro[j].x == p.x && micro[j].y == p.y) {
								// 미생물수를 비교한다.
								if(max > micro[j].n) {	// 현재 좌표의 미생물 수가 많으면
									// 미생물을 더하고 그 좌표의 군집을 죽인다.
									sum += micro[j].n;
									micro[j].alive = false;	
								} else {	// 다른 좌표의 미생물 수가 많으면
									// sum에 미생물 수를 더하고 max값을 그 좌표의 미생물 수로 바꾼다.
									// 방향도 큰 쪽의 방향으로 저장한다
									// 현재 좌표의 군집은 죽인다.
									sum += micro[j].n;
									max = micro[j].n;
									micro[idx].alive = false;
									idx = j;
								}
							} 
						}
						// 반복문을 빠져나오면 sum 에는 같은좌표에 있는 군집 미생물들이 모두 더해서 저장되어 있고
						// idx 에는 군집중에 가장 미생물수가 많은 군집이 저장되어 있다.
						// 그러므로 idx 인덱스에 있는 군집에 sum을 저장해준다.
						micro[idx].n = sum;
					}
//					System.out.println(i + " 번째 군집의 현재 상태 : " + " -----------> p.x : " + p.x + " / p.y :" + p.y + " / p.n : " + p.n + " / p.d : " + p.d);
				}
//				System.out.println();
			}
			
			for(int i=1; i<=micro.length-1; i++) {
				if(micro[i].alive) result += micro[i].n;
			}
			
			System.out.println("#" + tc + " " + result);
		}
	}
	
	
	public static boolean isOutside(int x, int y) {
		return x==0||y==0||x==N-1||y==N-1;
	}
	
	public static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
}

class Pair {
	int x;
	int y;
	int n;
	int d;
	boolean alive;
	
	Pair (int x, int y, int n, int d, boolean alive) {
		this.x=x;
		this.y=y;
		this.n=n;
		this.d=d;		
		this.alive = alive;
	}
}