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

문제

• SWEA 2382
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

이 문제는 시뮬레이션으로 문제에 주어진 조건을 크게 2가지로 나누어 생각하였다.

1. 미생물 이동
   군집이 이동할 다음 좌표가 약품에 닿으면 절반으로 줄어들고 방향을 바꾼다. 각 군집에 저장된 미생물 수는 Group클래스의 groups배열안 Bug클래스 형태로 저장한다.
2. 겹치는 군집의 미생물 합치기 모든 군집이 이동한 후에 미생물을 합친다. 이때, 한 좌표에 여러개의 미생물이 있을 경우 미생물수가 가장 큰 군집으로 합쳐준다.
   이를 위해 미생물 정보 Bug에 Comparable을 걸어주어서 각 좌표에 있는 군집 배열 groups를 오름차순한다.
   그럼 가장 첫번째 인덱스인 map[i][j].get(0) 군집이 미생물이 가장 많은 군집이 된다. 따라서 리스트에 있는 다른 군집들의 미생물을 모두 이 군집과 합치고 0으로 없애준다.
   
   미생물을 이동시키는것은 어렵지 않았지만, 미생물을 합치는 과정 속에서 어떻게 우선순위를 정해야 좋을지 오랜 고민이 필요한 문제였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
//미생물 격리
public class Solution {
     
    static int T;
    static int N, M, K; //셀의 개수, 격리 시간, 미생물 군집의 개수
    static Bug[] bugs; //미생물 정보 배열
    static Group[][] map; //군집정보
    static StringTokenizer st;
    static int[] di = {0, -1, 1, 0, 0}; //상하좌우
    static int[] dj = {0, 0, 0, -1, 1};
    static int Ans;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
         
        for(int tc=1; tc<=T; tc++) { //테스트케이스
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            bugs = new Bug[K+1];
            map = new Group[N][N];
            Ans = 0;
             
            for(int i=1; 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 dir = Integer.parseInt(st.nextToken());
                 
                bugs[i] = new Bug(i, x, y, count, dir); //미생물 1번~K번
            }
             
            int time = 0;
 
            while(time++ < M) { //격리 시간
                //현재 위치에 저장된 군집 정보 초기화
                for(int x=0; x<N; x++) {
                    for(int y=0; y<N; y++) {
                        map[x][y] = new Group(new ArrayList<>());
                    }
                }
                for(int i=1; i<=K; i++) {
                    //1. 미생물 이동
                    Bug bug = bugs[i];
                    if(bug.count == 0) continue; //이 군집에서 살아남은 미생물이 없으면 PASS
                    int nx = bug.x + di[bug.dir]; //다음 좌표
                    int ny = bug.y + dj[bug.dir];
                     
                    if(nx == 0 || nx == N-1 || ny == 0 || ny == N-1) { //약품에 닿으면
                        bug.count = bug.count / 2; //미생물 절반이 죽고
                        if(bug.count == 0) continue;
                        if(bug.dir == 1) bug.dir = 2; //이동방향 반대로
                        else if(bug.dir == 2) bug.dir = 1;
                        else if(bug.dir == 3) bug.dir = 4;
                        else if(bug.dir == 4) bug.dir = 3;
                    }
                    bug.x = nx; //다음 좌표로 이동
                    bug.y = ny;
                    map[nx][ny].groups.add(bug); //군집정보 새로 셋팅
                }
                 
                //2. 군집 미생물 합치기
                for(int i=0; i<N; i++) {
                    for(int j=0; j<N; j++) {
                        if(map[i][j].groups.size() >= 2) { //두개 이상의 군집이 한 셀에 모여있는 경우
                            Collections.sort(map[i][j].groups);
                            //미생물수가 가장 큰 애가 가장 처음에 있음
                            int Maxnum = map[i][j].groups.get(0).num; //미생물 수가 가장 많은 군집 번호
                            for(int idx=1; idx<map[i][j].groups.size(); idx++) {
                                bugs[Maxnum].count += map[i][j].groups.get(idx).count; //큰쪽에 합치고
                                bugs[map[i][j].groups.get(idx).num].count = 0; //비워준다.
                            }
                        }
                    }
                }
            }
 
            for(int i=1; i<=K; i++) {
                Ans += bugs[i].count;
            }
            System.out.println("#"+tc+" "+Ans);
        }
    }
     
    static class Group{
        ArrayList<Bug> groups; //군집번호
         
        public Group(ArrayList<Bug> groups) {
            this.groups = groups;
        }
    }
     
    static class Bug implements Comparable<Bug>{
        int num; //얘 군집 번호
        int x; //세로 위치(행)
        int y; //가로 위치(열)
        int count; //미생물 수
        int dir; //이동방향
         
        public Bug() {}
         
        public Bug(int num, int x, int y, int count, int dir) {
            this.num = num;
            this.x = x;
            this.y = y;
            this.count = count;
            this.dir = dir;
        }
 
        @Override
        public int compareTo(Bug o) { //미생물 수가 큰 순으로 정렬
            if(this.count > o.count) return -1;
            else return 1;
        }
    }
}