문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo&categoryId=AWXRFInKex8DFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98+sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

코드 (Java)

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

class Solution
{
	private static final int X = 0;
	private static final int Y = 1;
	private static final int DIR = 0;
	private static final int ENERGY = 1;
	private static final int[][] delta = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
	
	private static class AtomPos implements Comparable<AtomPos> {
		int X;
		int Y;

		@Override
		public int compareTo(Solution.AtomPos o) {
			if (Integer.compare(X, o.X) != 0) {
				return Integer.compare(X,  o.X);
			}
			return Integer.compare(Y, o.Y);
		}
		
		@Override
		public boolean equals(Object obj) {
			AtomPos objr = (AtomPos) obj;
			return objr.X == X && objr.Y == Y;
		}
		
		@Override
		public int hashCode() {
			return (X+2000)*4001 + (Y+2000);
		}
		
		public AtomPos() {
			X = -1;
			Y = -1;
		}
		
		public AtomPos(int x, int y) {
			X = x;
			Y = y;
		}
		
		
	}
	
	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++)
		{
			int N = Integer.parseInt(br.readLine().trim());
			int validCnt = N; //valid atoms alive.
			int energy = 0;
			AtomPos[] atomPos = new AtomPos[N];
			int[][] atomMeta = new int[N][2];
			boolean[] valid = new boolean[N];
			
			for (int atom = 0; atom < N; ++atom) {
				StringTokenizer st = new StringTokenizer(br.readLine().trim());
				atomPos[atom] = new AtomPos();
				atomPos[atom].X = Integer.parseInt(st.nextToken())*2;
				atomPos[atom].Y = Integer.parseInt(st.nextToken())*2;
				atomMeta[atom][DIR] = Integer.parseInt(st.nextToken());
				atomMeta[atom][ENERGY] = Integer.parseInt(st.nextToken());
//				System.out.printf("atom %d, X %d, Y %d, DIR %d, ENERGY %d\n", atom, atomPos[atom].X, atomPos[atom].Y, atomMeta[atom][DIR], atomMeta[atom][ENERGY]);
				valid[atom] = true;
			}
			
			//int iter = 0;
			while (validCnt > 1) { //if less than 2, no collision could happen.
//				System.out.println(validCnt);
				//++iter;
				Map<AtomPos, Integer> arbPos = new HashMap<>(); //for finding colliding atoms.
				
				for (int atom = 0; atom < N; ++atom) {
					if (!valid[atom]) continue; //that atom is not alive.
					
					int atomDir = atomMeta[atom][DIR];
					AtomPos newPos = new AtomPos(atomPos[atom].X + delta[atomDir][X], atomPos[atom].Y + delta[atomDir][Y]);
					atomPos[atom].X = newPos.X;
					atomPos[atom].Y = newPos.Y;
//					if (iter == 2000)
//						System.out.printf("atom: %d, newX : %d newY : %d\n", atom, newPos.X, newPos.Y);
					if (newPos.X < -2000 || newPos.X > 2000 || newPos.Y < -2000 || newPos.Y > 2000) {
						//went out of the field.
						validCnt--;
						valid[atom] = false;
					}
					else if (!arbPos.containsKey(newPos)) {
						//no collision~
						arbPos.put(newPos, atom);
					} else {
						//has collision...
//						System.out.println("hi");
						int relatedAtom = arbPos.get(newPos);
						if (valid[relatedAtom] != false) {
							validCnt--;
							valid[relatedAtom] = false;
							energy += atomMeta[relatedAtom][ENERGY];
						}
						validCnt--;
						valid[atom] = false;
						energy += atomMeta[atom][ENERGY];
					}
				}
			}
			
			bw.write("#" + test_case + " " + energy + '\n');
//			bw.flush();
		}
		
		bw.flush();
		bw.close();
	}
}

풀이

• 순수 구현/시뮬레이션 문제

• 자료구조 선택 및 초기 구상이 중요하다. 필자는 다음과 같이 수행

  • 0.5초 사이에 충돌하는 것이 가능하기에 좌표를 2배로 늘려서 매 iter마다 자연스럽게 이를 고려할 수 있도록 구상.
  • iter마다 HashMap을 형성. 중복 좌표를 찾기 위해, 그리고 찾았을 경우 중복이 아니라고 생각했던 atom을 역추적하기 위해 만듬.
    • 대소관계 비교를 할 필요가 없기 때문에 TreeMap을 사용하면 비효율적이며 실제로 통과하질 못한다.
    • HashMap 형성시 유의사항은 eqauls와 hashCode를 override해야 한다는 것이다. 안그러면 제대로 동작하질 못한다. 필자는 적절한 hashcode 형성에 문제의 범위 제한을 활용했다.
    • 단순히 모든 경우를 비교하는것도 매우 비효율적이다. (테스트당 N(N-1)4000 의 연산을 해야할 수도 있다.)