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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

SW Expert Academy

큐 사이즈만큼 반복문을 도는 내부에서 weight 정보를 담는 2차원 배열을 초기화시켜줬을때 메모리(105MB)와 실행시간(507ms)이 크게 나왔습니다.

생각

미생물의 좌표가 겹쳤을때 가장 큰 미생물의 군집의 방향으로 방향을 다시 설정해야하고 그 다음 이동에서 미생물의 개수는 모두 누적된 미생물의 총 개수입니다.

 

이 문제를 풀면서 미생물의 타입에 대해 엄청나게 고민했습니다. 이와 비슷한 낚시왕 문제에서는 상어를 이동시키고 가장 큰 상어가 해당 좌표의 상어로 단순하게 대체되기 때문에 미생물 격리보다 쉽게 풀 수 있었습니다.

 

1. List<Bacteria[][]>, Queue<Bacteria> 이 두가지로 각 좌표에 겹쳐지는 미생물들을 모두 넣고 빼자. 해당 좌표에서 가장 큰 미생물을 찾을때 간단하다. 하지만 이동 시킨다음 남아있는 미생물들을 삭제시키려면 추가적인 연산 필요.. 메모리도 불필요하게 많이 차지할껏 같음..

2. Bacteria [][], Queue<Bacteria>, int[][] weightBacteria 로 무게정보만 int 2차원 배열로 따로 누적해서 관리하자. 큐에는 이동 후 미생물들의 객체 정보를 업데이트 시켜서 넣어주면 됨. 정답도 Queue에 있는 박테리아의 무게를 누적하면 해결!

 

2번의 생각으로 문제를 풀었습니다.

 

1. 큐에 초기 박테리아 정보를 class로 만들어 추가합니다.

2. 큐가 빌때까지 1시간마다 진행되는 모든 미생물의 이동을 동시에 시켜줍니다. -> 큐의 사이즈만큼 내부에서 반복문을 돌면 동시에 이동하는 효과가 있습니다.

3. 박테리아 클래스의 내부에 move() 메소드를 만들어 다음 좌표가 약품이라면 방향을 반대로 바꿔주고, 미생물의 개수를 절반으로 줄여줍니다.

4-1. 새롭게 바뀐 y좌표와 x좌표를 가지고 map[ny][nx]가 null 이라면 map에 박테리아를 넣어줍니다. weightBacteria에 무게정보를 넣어줍니다.

4-2. 만약 map[ny][nx]가 null이 아니라면 이번 라운드에서 내가 이동한 박테리아가 이미 위치하고 있다는 뜻입니다. 기존에 이미 위치한 박테리아와 비교하여 큰 박테리아를 map에 넣어줍니다. 누적하는 무게를 관리하는 weightBacteria에 무게를 합산시켜줍니다.

5. 3~4번에서 1시간동안의 박테리아 이동이 끝났습니다. N*N 배열을 돌면서 map[y][x].cnt = weightBacteria[y][x] 로 업데이트 시켜줍니다. 군집 무게가 업데이트된 map[y][x]를 큐에 추가시켜줍니다.

6. map과 weightBacteria 의 원래 남아있던 정보를 모두 지워줍니다.

7. T초가 모두 경과한뒤 q가 빌때까지 반복하여 무게를 누적합니다.

 

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA_2382_미생물격리_Re {
	static int N,T,K;
	static Bacteria[][] map;
	static List<Bacteria> baterias;
	static Queue<Bacteria> q;
	static int[] dy = {0,-1,1,0,0}; // 상 하 좌 우
	static int[] dx = {0,0,0,-1,1};
	
	static class Bacteria{
		int y,x,dir,cnt; //개별무게
		public Bacteria(int y, int x, int dir, int cnt) {
			super();
			this.y = y;
			this.x = x;
			this.dir = dir;
			this.cnt = cnt;
		}
		
		public void move() {
			//약품이면 미생물 절반 죽고 이동 방향 반대로
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			
			if(ny == 0 || ny == N-1 || nx == 0 || nx == N-1) {
				this.cnt = this.cnt/2;
				switch (this.dir) {
					case 1:
						this.dir = 2;
						break;
					case 2:
						this.dir = 1;
						break;
					case 3:
						this.dir = 4;
						break;
					case 4:
						this.dir = 3;
						break;
				}
			}
			this.y = ny;
			this.x = nx;
		}

		@Override
		public String toString() {
			return "Bacteria [y=" + y + ", x=" + x + ", dir=" + dir + ", cnt=" + cnt + "]";
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		int TC = Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			T = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new Bacteria[N][N];
			
			q = new LinkedList<Bacteria>();
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine(), " ");

				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());
				int cnt = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken());
				Bacteria b = new Bacteria(y,x,dir,cnt);

				q.add(b);

			}
			sb.append("#").append(t).append(" ").append(solve()).append("\n");
			
		}
		System.out.println(sb);

	}
	
	private static int solve() {
		
		int[][] weightBacteria = new int[N][N];
		
		//큐에는 이동 후의 미생물 객체 정보만 담아논다
		//무게정보는 int[][] 로 따로 관리
		while (!q.isEmpty()) {
			if(T==0) break;

			int size = q.size();
			while(size-- > 0) {
				Bacteria b = q.poll();
				int y = b.y;
				int x = b.x;
				
				b.move(); // 이동
				
				int ny = b.y; // 새로운 y 좌표 
				int nx = b.x; // 새로운 x 좌표 
				
				if(b.cnt > 0) {
					if(map[ny][nx] == null) {
						weightBacteria[ny][nx] = b.cnt;
						map[ny][nx] = b;
						
					}else {
						if(map[ny][nx].cnt < b.cnt) {
							map[ny][nx] = b;
						}
						weightBacteria[ny][nx] += b.cnt; // 여기서 미생물 크기 누적해준다
					}
				}
			}// 이동 완료
			//print(weightBacteria);
			
			//다음 큐에 (방향,무게 누적)업데이트 한 최종 정보 담기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(map[i][j] != null) {
						map[i][j].cnt = weightBacteria[i][j]; // 한번 이동이 끝나고 미생물 누적 값 -> 개별 무게로 업데이트
						q.add(map[i][j]); // 군집 무게 업데이트한 정보 담아서 큐에 넣어준다
						
						map[i][j] = null; // 원래 정보 지워주기
						weightBacteria[i][j] = 0; // 무게 정보 지워주기
					}
				}
			}	
			T--;
		}
		
		int sum = 0;
		while(!q.isEmpty()) {
			sum += q.poll().cnt;
		}

		return sum;
	}
	private static void print(int[][] weightBacteria) {
		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();
	}
}