[SWEA] 2382. 미생물 격리 (시뮬레이션/Java)

[SWEA] 2382. 미생물 격리

 

📌 풀이 과정

미생물 군집의 정보를 입력받아 저장해야 하는데

미생물 수가 큰 순서대로 정렬하도록 PriorityQueue를 사용한다.

우선순위 큐를 사용하면서 두 개 이상의 군집이 한 셀에 모이는 경우는 미생물 수를 합치는 로직만 구현해주면 된다.

 

1. 매 시간마다 이동 후의 군집 상태를 저장하기 위해 map 배열을 초기화 한다.

2. 각 미생물 군집을 꺼내서 현재 방향에 맞게 이동한다.

3. 이동 후 군집 상태를 다시 우선순위 큐에 넣는다.

• 이동 후, 격자의 경계에 도달하면 미생물 수를 절반으로 줄이고 이동 방향을 반대로 바꿉니다.
• 이동한 위치에 다른 군집이 존재하면 미생물 수를 합칩니다.

4. 이동 후의 군집 상태를 다시 우선순위 큐에 넣는다.

 

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {

	static int N, M, K;
	static int[] dx = { -1, 1, 0, 0 }; // 상하좌우
	static int[] dy = { 0, 0, -1, 1 };
	static Group[][] map;
	static PriorityQueue<Group> groupQ;

	static class Group implements Comparable<Group> {
		int x, y, micro, dir;

		Group(int x, int y, int micro, int dir) {
			this.x = x;
			this.y = y;
			this.micro = micro;
			this.dir = dir;
		}

		@Override
		public int compareTo(Group o) {
			return o.micro - this.micro; // 미생물 수가 큰 순서대로 정렬
		};
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 셀의 개수
			M = Integer.parseInt(st.nextToken()); // 격리 시간
			K = Integer.parseInt(st.nextToken()); // 미생물 군집의 개수
			groupQ = new PriorityQueue<>();
			map = new Group[N][N];

			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 micro = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken()) - 1; // 상(0), 하(1), 좌(2), 우(3)
				Group group = new Group(x, y, micro, dir);
				groupQ.add(group);
			}

			for (int i = 1; i <= M; i++) {
				initMap();
				isolation();
				getCell();
			}

			int total = 0;
			for (Group g : groupQ) {
				total += g.micro;
			}

			sb.append("#" + tc + " " + total + "\n");
		}
		System.out.print(sb);
	}

	private static void initMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = null;
			}
		}
	}

	private static void getCell() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == null)
					continue;
				groupQ.add(map[i][j]);
			}
		}
	}

	private static void isolation() {
		PriorityQueue<Group> moveQ = new PriorityQueue<>();

		while (!groupQ.isEmpty()) { // 모든 군집 이동 처리
			Group cur = groupQ.poll();
			int nx = cur.x + dx[cur.dir]; // 다음으로 이동할 위치
			int ny = cur.y + dy[cur.dir];

			if (nx == 0 || ny == 0 || nx == N - 1 || ny == N - 1) {
				cur.micro /= 2;
				switch (cur.dir) { // 이동 방향 반대로 변경
				case 0: cur.dir = 1; break;
				case 1: cur.dir = 0; break;
				case 2: cur.dir = 3; break;
				case 3: cur.dir = 2; break;
				}
			}

			if (cur.micro > 0) {
				cur.x = nx;
				cur.y = ny;
				moveQ.add(cur);
			}
		}

		while (!moveQ.isEmpty()) {
			Group cur = moveQ.poll();

			if (map[cur.x][cur.y] == null) {
				map[cur.x][cur.y] = cur;
			} else {
				map[cur.x][cur.y].micro += cur.micro;
			}
		}
	}

}