(JAVA) 5648. [모의 SW 역량테스트] 원자 소멸 시뮬레이션

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

완전 명쾌하게 풀었다고 하긴 좀 거시기하긴 한데……
나름대로 머리를 굴려서 (?) 풀긴 풀었음.
– 1초마다 1씩 이동을 한다고 했는데, 거리가 1일 경우 중간지점에서 충돌하는 경우도 있어서 0.5초 단위로 계산하게 함 (이로 인해 루프 횟수가 2배로 늘어나는 게 함정…)
– 정수로 계산하게 하려고 거리 정보를 2배씩 곱함. 즉 0.5초마다 1씩 움직이는걸로 (=1초마다 2씩 움직임) 계산을 고침.
– 매 0.5초마다 원소를 이동시킨 후, 각 원소의 위치를 List에 투입. 이후 각 원소의 위치가 List에 이미 있는지 확인 후, 이미 있으면 해당하는 원소들을 모두 폭발 처리 (원소 에너지는 0으로, 원래 에너지는 총 에너지에 합산)
– 20번 (=10초)마다 충돌 가능성이 없는 원소를 제외하는 로직 추가 (20번마다 하는 이유는 제외하는 로직의 시간이 오래 걸리기 때문에.. 하지만 이 로직이 아예 없으면 최대 거리 기준으로 루프가 돌아가기 때문에 또 오래 걸린다는 문제가 있으므로 적당한 밸런스 조절)

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

public class Solution {
	public static final int xBound = 2000, yBound = 2000;
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");

				int numN = Integer.parseInt(reader.readLine()); // 원자 수 
				
				int[] xAtom = new int[numN]; // 원자 X 위치 
				int[] yAtom = new int[numN]; // 원자 Y 위치
				int[] directionAtom = new int[numN]; // 원자 이동방향
				int[] energyAtom = new int[numN]; // 원자 에너지
				
				for (int i = 0; i < numN; i++) {
					String[] tmp = reader.readLine().split(" ");
					
					xAtom[i] = 2 * Integer.parseInt(tmp[0]); // -1000~1000을 -2000~2000으로 스케일링 (0.5초 당 1씩 움직이는 걸로 환산)
					yAtom[i] = 2 * Integer.parseInt(tmp[1]); // -1000~1000을 -2000~2000으로 스케일링 (0.5초 당 1씩 움직이는 걸로 환산) 
					directionAtom[i] = Integer.parseInt(tmp[2]); // 0: 상, 1: 하, 2: 좌, 3: 우
					energyAtom[i] = Integer.parseInt(tmp[3]);
				}
				
				int answer = 0;
				
				// 8000: 2*(2000-(-2000)), 즉 가장 먼 거리 기준으로 계산
				for (int i = 0; i < 4 * xBound; i++) {
					boolean allReachedEnd = true;

					Map<String, Integer> isFound = new HashMap<String, Integer>();
					
					// 충돌 가능성 없으면 미리 배제 
					if (i % 20 == 0) { // 20번에 한 번 빈도로만 수행 (시간이 오래 걸리기 때문에)
						for (int j = 0; j < numN; j++) {
							if (energyAtom[j] == 0) // 이미 폭발한 경우 확인하지 않음
								continue;
	
							boolean toEscape = false;
	
							for (int k = 0; k < numN; k++) {
								if (j == k) // 같은 경우는 계산하지 않음 
									continue;
															
								switch (directionAtom[j]) {
								case 0: // 상 
									if (yAtom[j] < yAtom[k]) { // 더 위에  
										if (directionAtom[k] == 1) // 아래로 내려오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 2 || directionAtom[k] == 3) { // 좌나 우로 이동하고,
											if (yAtom[k] - yAtom[j] == Math.abs(xAtom[k] - xAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								case 1: // 하
									if (yAtom[j] > yAtom[k]) { // 더 아래에  
										if (directionAtom[k] == 0) // 아래로 내려오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 2 || directionAtom[k] == 3) { // 좌나 우로 이동하고,
											if (yAtom[j] - yAtom[k] == Math.abs(xAtom[k] - xAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								case 2: // 좌
									if (xAtom[j] > xAtom[k]) { // 더 왼쪽에  
										if (directionAtom[k] == 3) // 오른쪽으로 오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 0 || directionAtom[k] == 1) { // 좌나 우로 이동하고,
											if (xAtom[j] - xAtom[k] == Math.abs(yAtom[k] - yAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								case 3: // 우 
									if (xAtom[j] < xAtom[k]) { // 더 오른쪽에  
										if (directionAtom[k] == 2) // 왼쪽으로 오는 원소가 있을 경우
											toEscape = true;
										else if (directionAtom[k] == 0 || directionAtom[k] == 1) { // 좌나 우로 이동하고,
											if (xAtom[k] - xAtom[j] == Math.abs(yAtom[k] - yAtom[j])) // 만날 가능성이 있을 때
												toEscape = true;
										}
									}
									break;
								}
								
								// 충돌 가능성이 있으면 더 이상 진행하지 않음
								if (toEscape == true)
									break;
							}
							// 충돌 가능성이 없으면 에너지를 0으로 처리 (넣을 일이 없음)
							if (toEscape == false)
								energyAtom[j] = 0;
						}
					}
					
					// 각 원소 이동시킴
					for (int j = 0; j < numN; j++) {
						if (energyAtom[j] == 0) // 이미 폭발한 경우 확인하지 않음
							continue;

						allReachedEnd = false;
						
						switch (directionAtom[j]) {
						case 0: // 상 
							yAtom[j]++;
							break;
						case 1: // 하
							yAtom[j]--;
							break;
						case 2: // 좌
							xAtom[j]--;
							break;
						case 3: // 우 
							xAtom[j]++;
							break;
						}
						
						String key = xAtom[j] + "/" + yAtom[j];
						// 이미 겹치는 위치가 있음
						if (isFound.containsKey(key) == true) {
							int firstAtom = isFound.get(key);
							if (energyAtom[firstAtom] != 0) {
								answer += energyAtom[firstAtom];
								energyAtom[firstAtom] = 0;
							}
							
							answer += energyAtom[j];
							energyAtom[j] = 0;								
						}
						else
							isFound.put(key, j);
					}
					
					// 모든 원소가 더 이상 이동안될 경우 중단 
					if (allReachedEnd == true)
						break;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.