[SWEA] 2382번 미생물 격리 - 자바

접근 방법

1. 핵심 로직 : 미생물을 모두 이동시킨 후에 합쳐질 수 있는 미생물에 대해 처리

2. 미생물이 충돌하는 경우(같은 좌표인 경우)에 대해 확인하기 위해 Collections.sort를 사용하여 같은 좌표에 대해 모여있을 수 있도록 하였습니다.

 

구현 설명

• LinkedList<Pair> locations : 미생물의 좌표를 저장하는 리스트입니다. 

구현 시 주의 사항

• 리스트를 사용하면서 미생물을 처리하는 과정에서 remove함수를 사용하게 됩니다. 이때 인덱스에 대해서도 -1 해주어야 합니다. 그렇지 않으면, 처리하는 과정에서 일부 요소가 누락될 수 있습니다. List의 논리적 크기는 고정되어 있지 않으며, List에 있는 요소의 삽입이나 삭제에 따라 변경됩니다.

구현하며 어려웠던 점

• sort를 위해 compareto에서 조건으로 x좌표와 y좌표가 같은 경우에 대해 미생물 수를 기준으로 내림차순을 진행하였습니다. 그 외의 경우에 대해서는 x좌표 기준 오름차순을 진행하였습니다. 하지만, 이 과정에서 분명 x, y좌표가 같은 미생물 들임에도 불구하고 제대로 sort가 되지 않았습니다. 따라서, 추가적으로 x좌표가 같은 경우에 대해 y좌표 기준 오름차순을 진행을 통해 모든 좌표에 대해 제대로 sort가 이루어질 수 있었습니다.

package swea.p2382;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution_2382 {
	
	private static int[][] dir = {{0, 0},{-1,0}, {1,0},{0,-1},{0,1}};//상하좌우
	private static int result;
	private static LinkedList<Pair> locations;
	
	static class Pair implements Comparable<Pair>{
		int x;
		int y;
		int value;//미생물 수
		int move_dir;//이동방향, (상: 1, 하: 2, 좌: 3, 우: 4)
		
		public Pair(int x, int y, int value, int move_dir) {
			this.x = x;
			this.y = y;
			this.value = value;
			this.move_dir = move_dir;
		}

		@Override
		public int compareTo(Pair o) {
			if(this.x==o.x && this.y == o.y) {
				return -(this.value - o.value);
			}
			if(this.x == o.x) 
				return this.y - o.y;
			
			return this.x - o.x;
		}

		@Override
		public String toString() {
			return "Pair [x=" + x + ", y=" + y + ", value=" + value + ", move_dir=" + move_dir + "]";
		}
		
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		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());
			int N = Integer.parseInt(st.nextToken());//셀의 개수
			int M = Integer.parseInt(st.nextToken());//격리 시간
			int K = Integer.parseInt(st.nextToken());//미생물 군집의 개수
			
			locations = new LinkedList<Pair>();
			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 size = Integer.parseInt(st.nextToken());
				int direction = Integer.parseInt(st.nextToken());

				locations.add(new Pair(x, y, size, direction));
			}
			solve(M, N);
			
			System.out.println("#" + test_case + " " + result);
		}
	}
	
	
	//로직 : 모든 미생물 이동시킨 후에 합쳐지는 미생물 처리하기
	private static void solve(int M, int N) {
		while(M-- > 0) {

			for (int i = 0; i < locations.size(); i++) {
				Pair now = locations.get(i);
				int nowX = now.x;
				int nowY = now.y;
				int nowValue = now.value;
				int nowDir = now.move_dir;
				
				int nextX = nowX + dir[nowDir][0];
				int nextY = nowY + dir[nowDir][1];
				int nextDir = 0;
				
				if(nextX == 0 || nextY == 0 || nextX >= N-1 || nextY >= N-1) {//약품이 칠해진 구역(가장 자리의 빨간 셀)
					if(nowDir == 1) nextDir = 2;
					else if(nowDir == 2) nextDir = 1;
					else if(nowDir == 3) nextDir = 4;
					else nextDir = 3;
					
					now.move_dir = nextDir;
					now.value /= 2;
					
					if(now.value <= 0) {//미생물 죽음 
						locations.remove(i);
						i--;
					}else {
						now.x = nextX;
						now.y = nextY;
					}
				}else {	
					now.x = nextX;
					now.y = nextY;
				}
				
			} 
		
			Collections.sort(locations);
			
			//합쳐지는 미생물 처리하기 
			combine(locations);
			
		}
		
		result = count(locations);
	}
	
	//합쳐지는 미생물 처리하기
	//같은 좌표에 대해 미생물 개수를 기준으로 내림차순-> 맨 앞의 좌표가 가장 개수가 크므로, 방향은 맨 앞을 기준으로 따름
	private static void combine(LinkedList<Pair> temp) {
		
		for (int i = 0; i < temp.size(); i++) {
			
			int sum = temp.get(i).value;
			int start = i;
			//같은 좌표  미생물 찾기
			while(i+1 < temp.size() && temp.get(i).x - temp.get(i+1).x == 0  && temp.get(i).y - temp.get(i+1).y == 0) {
				sum += temp.get(i+1).value;
				i++;
			}                                       
			
			//합치기
			//우선 순위에 따라 맨 앞의 요소가  방향이 큰 값이므로 방향에 대한 수정은 필요 X			
 			temp.get(start).value = sum;
 			
 			
			for (int j = start+1; j <= i; j++) {
				temp.remove(j);
				i--;
				j--;
			}

		}
			
	}
	
	private static int count(LinkedList<Pair> temp) {
		int sum = 0;
		for (int i = 0; i < temp.size(); i++) {
			sum += temp.get(i).value;
		}
		
		return sum;
	}
	
}