SWEA [모의 SW 역량테스트] 미생물 격리 [Java]

문제

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

SW Expert Academy

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; //상 : 1  하 : 2  좌 : 3 우 : 4
    static int N, M, K;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); //구역 크기
            M = Integer.parseInt(st.nextToken()); //격리 시간
            K = Integer.parseInt(st.nextToken()); //미생물 군집의 개수
            Map<Integer, Micro>[][] position = new HashMap[N][N];
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    position[i][j] = new HashMap<>();
                }
            }
            Map<Integer, Micro> microList = new HashMap<>();
            int idx = 1;
            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 count = Integer.parseInt(st.nextToken());
                int direction = Integer.parseInt(st.nextToken());
                microList.put(idx++, new Micro(x, y, count, direction));
            }
            //입력 끝*************************************************************
             
            for(int time = 1; time <= M; time++) {
                List<Integer> removeKey = new ArrayList<>();
                for(int nowKey : microList.keySet()) {
                    Micro now = microList.get(nowKey);
                    int nx = now.x + dx[now.direction - 1];
                    int ny = now.y + dy[now.direction - 1];
                     
                    if(isInRedZone(nx, ny)) {
                        now.count /= 2; //미생물 절반 죽이기
                        if(now.count == 0) { //0이 된 애들 사라져야됨
                            removeKey.add(nowKey);
                            continue;
                        }
                        //이동 방향 반대로 바꾸기
                        if(now.direction == 1) now.direction = 2;
                        else if(now.direction == 2) now.direction = 1;
                        else if(now.direction == 3) now.direction = 4;
                        else if(now.direction == 4) now.direction = 3;
                    }
                     
                    now.x = nx;
                    now.y = ny;
                    position[nx][ny].put(nowKey, now);
                }
                for(int key : removeKey) {//count 0인애들 삭제
                    microList.remove(key);
                }
                for(int i = 0; i < N; i++) {
                    for(int j = 0; j < N; j++) {
                        if(position[i][j].size() > 1) {//미생물이 만남
                            Micro maxMicro = null;
                            int sumCount = 0;
                            int[] tmpMicroKeys = new int[position[i][j].size()]; //삭제 시킬 애들 저장
                            int tmp = 0;
                            for(int positionKey : position[i][j].keySet()) {
                                sumCount += position[i][j].get(positionKey).count;
                                if(maxMicro == null) maxMicro = position[i][j].get(positionKey);
                                if(position[i][j].get(positionKey).count > maxMicro.count) maxMicro = position[i][j].get(positionKey);
                                tmpMicroKeys[tmp++] = positionKey;
                            }
                       
                            //합쳐서 새로운 군집 만들고 나머지 군집 모두 삭제 시키기
                            for(int key : tmpMicroKeys) { //삭제
                                microList.remove(key);
                            }
                            microList.put(idx++, new Micro(i, j, sumCount, maxMicro.direction)); //새로운 군집 저장
                        }
                        position[i][j].clear();
                    }
                }
            }
             
            int answer = 0;
            for(int key : microList.keySet()) {
                answer += microList.get(key).count;
            }
            //System.out.println(answer);
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
     
    static boolean isInRedZone(int x, int y) {
        if(x == 0 || x == N - 1 || y == 0 || y == N - 1) return true;
        return false;
    }
 
}
class Micro{
    int x;
    int y;
    int count;
    int direction;
    public Micro(int x, int y, int count, int direction) {
        this.x = x;
        this.y = y;
        this.count = count;
        this.direction = direction;
    }
     
}

 

시뮬레이션 문제이기 때문에 조건을 먼저 잘 정립해주었다.

 

1.배열의 가장자리에 도달하면 미생물의 수가 반으로 줄어든다. 이때 미생물의 수가 홀수라면 소수점을 버리기 때문에 그냥 미생물 수 / 2 연산을 해주면 된다는 뜻

2. 미생물의 수가 0이 되면 해당 군집은 사라진다.

3. 두개 이상의 군집이 한 위치에 모이게되면 가장 수가 많은 쪽으로 흡수된다.

 

먼저 미생물 군집을 표현하는 Micro라는 클래스를 만들어 주었다.

각 미생물의 위치를 저장해줄 Map의 2차원 배열을 선언 해주었다.

미생물 군집을 Map으로 저장해주는 이유는 각 군집을 구분하는게 헷갈려서 그렇게 했는데 메모리 초과가 안나서 다행이라고 생각했다.