[SWEA 2382] 미생물 격리 (Java)

SWEA 2382 미생물 격리

문제풀이

시뮬레이션 문제로 문제에서 시키는대로만 구현하면 가뿐하게 풀어낼 수 있는 문제다. 하지만 항상 늘 그렇듯이 문제를 마음대로 해석해버린다...

기본적인 틀은 다음과 같다.

• 다음을 시간만큼 반복한다.
  • 군집들을 이동시킨다.
    • 약품처리된 지역이 아닐경우
      • 이동할 위치에 다른 군집이 없을 경우 이동한다.
      • 이동할 위치에 다른 군집이 있을 경우 조건에 맞게 처리한다.
    • 약품처리된 지역일 경우
      • 조건에 맞게 미생물을 반감시키고 군집의 방향을 바꾼다.

다음과 같은 특징을 가진다.

• 이 문제는 군집들을 중심으로 이루어진다. 따라서 BFS 문제처럼 전체 Map을 계속 가지고 있을 필요가 없다. 특정 시간동안 이동한 군집이 겹치는지 확인하기 위해서 Map을 사용한다. 따라서 매 시간마다 새로운 Map이 필요하다.
• 군집이 가지는 정보가 많기 때문에 클래스로 관리하면 좋다. 또한 몇가지 편의 매서드를 만들어두면 좋다. (방향 바꾸기, 미생물 반감시키기, 좌표 설정)
• 반복문 수행중에 군집의 삭제가 진행되기 때문에 Collection을 사용하면 문제가 발생하여 별도의 처리가 필요했다. 따라서 단순 배열을 사용하는 것이 가장 깔끔했다.

사실 여기까지는 쉽게 구현했다. 그런데 계속해서 두 개의 테스트케이스가 틀리는 것이 아닌가... 정말 답답해서 미칠것 같았다. 문제는 다음과 같았다.

• Map의 특정 지점에 이미 군집이 존재하면 두 군집의 미생물을 비교하여 방향을 정하고 두 군집의 미생물을 더하여 총량을 업데이트 하였다. 여기서 문제가 발생했다. 3개 이상의 군집이 겹칠시에 먼저 처리된 군집들의 미생물량이 계속 업데이트 되면서 최종 방향이 제대로 설정되지 않았다.
• 따라서 겹친 군집을 모두 저장하였다가 이동이 모두 종료된 후에 처리해주는 방식으로 해결하였다.

문제를 꼼꼼하게 잘 읽자!!!

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Solution {
	
	static class Node {
		int id, r, c, cnt, d;
		
		Node(int id, int r, int c, int cnt, int d){
			this.id = id;
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.d = d;
		}
		
		public void setPos(int r, int c) {
			this.r = r;
			this.c = c;
		}
		
		public void reverse() {
			this.d = (d + 2) % 4;
		}
		
		public void half() {
			if(this.cnt % 2 == 0) {
				this.cnt = cnt / 2;
			} else {
				this.cnt = (int)Math.floor((double)(cnt / 2));
			}
		}
	}
	
	static HashMap<Integer, ArrayList<Node>> dupMap;
	static Node[] nodes;
	static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
	static int N, M, K, T, ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for(int t = 1 ; t <= T ; ++t) {
			st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			nodes = new Node[K + 1];
			dupMap = new HashMap<>();
			
			ans = 0;
			
			for(int k = 1 ; k <= K ; ++k) {
				st = new StringTokenizer(br.readLine());
				int r = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int cnt = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				
				// 상 하 좌 우 
				// 1 2 3 4 (입력 데이터) 
				// 0 2 1 3 (변형 데이터) 
				if(d == 1) d = 0;
				else if(d == 3) d = 1;
				else if(d == 4) d = 3;
				
				nodes[k] = new Node(k, r, c, cnt, d);
			}
			
			// 시뮬레이션 시작
			for(int i = 0 ; i < M ; ++i) {
				int[][] map = new int[N][N];
				
				// 전체 노드 순차 진행
				for(int id = 1 ; id <= K ; ++id) {
					if(nodes[id] == null) continue;
					
					Node cur = nodes[id];
					int nr = cur.r + dir[cur.d][0];
					int nc = cur.c + dir[cur.d][1];
					
					// 약품에 닿지 않았을 때
					if(nr >= 1 && nr <= N - 2 && nc >= 1 && nc <= N - 2) {
						int nid = map[nr][nc];
						
						// 다음 이동 지역에 아무것도 없을 때 
						if(nid == 0) {
							cur.setPos(nr, nc);
							map[nr][nc] = id;
						} else {
							// 다음 이동 지역에 이미 군집이 있을 때 
							Node other = nodes[nid];
							int key = nr * N + nc;
							
							if(dupMap.containsKey(key)) {
								ArrayList<Node> list = dupMap.get(key);
								cur.setPos(nr, nc);
								list.add(cur);
							} else {
								ArrayList<Node> list = new ArrayList<>();
								cur.setPos(nr, nc);
								list.add(other);
								list.add(cur);
								dupMap.put(key, list);
							}
						}
					} else {
						// 약품에 닿았을 때 
						if(cur.cnt == 1) {
							nodes[id] = null;
						} else {
							cur.half();
							cur.reverse();
							cur.setPos(nr, nc);
							map[nr][nc] = id;
						}
					}
				}
				
				// 같은 칸에 모인 군집들 처리하기 
				for(ArrayList<Node> list : dupMap.values()) {
					int total = 0;
					int max = 0;
					int maxId = -1;
					
					for(Node node : list) {
						total += node.cnt;
						
						if(node.cnt > max) {
							max = node.cnt;
							maxId = node.id;
						}
					}
					
					nodes[maxId].cnt = total;
					
					for(Node node : list) {
						if(node.id == maxId) continue;
						nodes[node.id] = null;
					}
				}
				
				dupMap.clear();
			}
			
			for(int i = 1 ; i <= K ; ++i) {
				if(nodes[i] == null) continue;
				ans += nodes[i].cnt;
			}
			
			System.out.println("#" + t + " " + ans);
		}
	}
}