[Java] 2382. 미생물 격리

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

 

문제 출처:  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

SW Expert Academy

 

 

군집이 합쳐질때의 방향은 미생물의 수에 대하여 내림차순으로 정렬 후 순차적으로 계산하는 방법으로 신경쓰지 않고 해결할 수 있었다.

 

전체 소스코드 아래 추가적인 설명이 있습니다. 

 

---

1. 전체 소스코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {

	static class Microbe {
		int x, y;
		int power;
		int dir;

		public Microbe(int x, int y, int power, int dir) {
			this.x = x;
			this.y = y;
			this.power = power;
			this.dir = dir;
		}
	}

	static int N, M, K;
	static int[][] map;
	static List<Microbe> microbes = new LinkedList<>();
	// (상: 1, 하: 2, 좌: 3, 우: 4)
	static int[][] dir = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			microbes.clear();

			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				microbes.add(new Microbe(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
						Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			}
			
			for (int day = 0; day < M; day++) {
				int lIdx = 0;
				List<Microbe> lists = new ArrayList<>();
				map = new int[N][N];
				for (int i = 0; i < N; i++) {
					Arrays.fill(map[i], -1);
				}

				microbes.sort(new Comparator<Microbe>() {
					public int compare(Microbe m1, Microbe m2) {
						return m2.power - m1.power;
					}
				});
				for (int mIdx = 0; mIdx < microbes.size(); mIdx++) {
					Microbe m = microbes.get(mIdx);
					int curDir = m.dir;
					int nextX = m.x + dir[m.dir][0];
					int nextY = m.y + dir[m.dir][1];
					
					m.x = nextX;
					m.y = nextY;
					
					if (isEdge(nextX, nextY)) { // power절반, 방향 반대
						m.power/=2;
						m.dir = getReversedDir(curDir);
					}
					
					if (map[nextX][nextY] == -1) {
						lists.add(m);
						map[nextX][nextY] = lIdx++;
					} else {
						lists.get(map[nextX][nextY]).power += m.power;
					}
				}
				
				microbes.clear();
				microbes.addAll(lists);
			}
			
			System.out.println("#" + test_case + " "+microbes.stream().mapToInt(m -> m.power).sum());
		}
	}

	// (상: 1, 하: 2, 좌: 3, 우: 4)
	private static int getReversedDir(int curDir) {
		if (curDir%2 == 0)
			return curDir - 1;
		else 
			return curDir + 1;
	}

	private static boolean isEdge(int nextX, int nextY) {
		if (nextX == 0 || nextX == N - 1 || nextY == 0 || nextY == N - 1)
			return true;
		else
			return false;
	}

}

---

2. 풀이

 

input에서 오는 미생물의 정보를 객체로 만들어 저장한다. 위치와 미생물의 수, 방향을 저장한 후, 미생물을 수가 가장 많은 순서로 정렬 후 하나씩 꺼내어 다음 위치로 이동시키며 이때 테두리에 도착한다면 미생물의 수를 절반으로 줄인 후 이동방향을 뒤집는다.

 

하루가 지나면 모든 미생물에 대해 같은 위치에 존재하는 군집들의 미생물 수를 합쳐준다. 모든 이동은 미생물의 수로 내림차순 정렬 후 순차적으로 진행한다. 그렇기 때문에 가장 숫자가 많은 군집의 방향이 먼저 그 자리를 차지한 군집이기 때문에 방향이 아닌 숫자만 더해준다.

 

위작업을 M번 반복한 후 남은 군집에 대하여 미생물의 수를 더하여 출력하였다.