문제

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

코드 (Java)

import java.util.*;
import java.io.*;

class Solution
{
	private static final int NUM = 0;
	private static final int DIRIDX = 1;
	private static final int ROW = 2;
	private static final int COL = 3;
	private static final int VALID = 4;
	private static final int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	private static int N;
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			int[][] microbes = new int[K][5];
			
			for (int i = 0; i < K; ++i) {
				st = new StringTokenizer(br.readLine().trim());
				microbes[i][ROW] = Integer.parseInt(st.nextToken());
				microbes[i][COL] = Integer.parseInt(st.nextToken());
				microbes[i][NUM] = Integer.parseInt(st.nextToken());
				microbes[i][DIRIDX] = Integer.parseInt(st.nextToken()) - 1;
				microbes[i][VALID] = 1;
			}
			
			//simulate
			while (M > 0) {			
				M--;
				HashMap<Integer, ArrayList<Integer>> allNextPos = new HashMap<>();
				for (int i = 0; i < K; ++i) {
					if (microbes[i][VALID] != 1) continue; //not valid
					microbes[i][ROW] += delta[microbes[i][DIRIDX]][0];
					microbes[i][COL] += delta[microbes[i][DIRIDX]][1];
					if (microbes[i][ROW] == 0 || microbes[i][ROW] == N-1 || microbes[i][COL] == 0 || microbes[i][COL] == N-1) {
						//met barrier
						microbes[i][DIRIDX] = changeDir(microbes[i][DIRIDX]);
						microbes[i][NUM] /= 2;
						if (microbes[i][NUM] == 0) {
							microbes[i][VALID] = 0;
							continue;
						}
					}
					
					int key = makeKey(microbes[i][ROW], microbes[i][COL]);
					
					//some works related to prepare merging
					if (!allNextPos.containsKey(key)) {
						allNextPos.put(key, new ArrayList<>());
					}
					
					allNextPos.get(key).add(i);
				}
				
				//do merging if needed
				Set<Integer> keys = allNextPos.keySet();
				for (int key : keys) {
					ArrayList<Integer> microbeIndices = allNextPos.get(key);
					if (microbeIndices.size() > 1) { //need to merge.
						int maxIdx = -1;
						int maxVal = -1;
						for (int idx : microbeIndices) { //select the remaining microbe
							if (microbes[idx][NUM] > maxVal) {
								maxIdx = idx;
								maxVal = microbes[idx][NUM];
							}
						}
						
						for (int idx : microbeIndices) { //merge microbes
							if (idx != maxIdx) {
								microbes[maxIdx][NUM] += microbes[idx][NUM];
								microbes[idx][VALID] = 0;
							}
						}
					}
				}
			}
			
			int remainingMicrobes = 0;
			
			for (int i = 0; i < K; ++i) {
				if (microbes[i][VALID] == 1) {
					remainingMicrobes += microbes[i][NUM];
				}
			}
			
			bw.write("#" + test_case + " " + remainingMicrobes + "\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
	
	private static int makeKey(int row, int col) {
		return row * N + col;
	}
	
	private static int changeDir(int idx) {
		switch(idx) {
			case 0:
				return 1;
			case 1:
				return 0;
			case 2:
				return 3;
			default:
				return 2;
		}
	}
}

풀이

• 시뮬레이션. 구상을 잘 하는 것이 중요하다.
  • 처음에 배열을 만들어서 각 위치별로 미생물이 누가 존재하는지를 추적할까 했지만 만났을 때 어떻게 처리하는지가 복잡해서 다른 방법을 생각하기로 결정.
  • 변동된 후 위치를 HashMap에다가 모아넣고, 중복된 위치에 해당하는 미생물들을 HashMap 안에서 보관중인 각 ArrayList에서 보유하도록 했다.
  • 거기에 미생물 idx가 있는데, 이 idx를 기반으로 merge될 미생물들을 찾아가지고 어떻게 merge 할지 정하는 것이 가능.
  • 그 외에도 미생물 메타데이터를 활용해서 방향 전환, 개수 조절, 소멸 등을 관리했다.
  • 다만 이러니까 메모리 소모가 많다. 그럴만한것이 아예 모이는 미생물이 없으면 1000개의 ArrayList가 형성되기 때문. 사실 이것의 개선은 간단한데, ArrayList 대신 int array를 HashMap에서 저장하고, 중복되는 위치가 등장할때마다 원래 microbe를 가지고 비교를 하면서 merging을 하면 된다.