[Java] SWEA 미생물 격리

1. 문제분석

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

SW Expert Academy

방향이 있는 미생물이 움직이는데 가장자리에 닿는다면 방향이 바뀌고 미생물의 크기가 반으로 줄어든다.

 

필자는 처음에 미생물 클래스 배열을 만들어서 모든 움직임으로 관리할려고 했다.

이렇게 되니 swap도 해야하고 미생물을 움직이는 것도 이상해져서 다른 방법을 찾아보았다.

 

다음은 큐를 활용해서 한개를 꺼내서 2차원 객체 배열에서 상태를 관리할려고 했다.

하지만 모든 큐를 비교하지 못했고 배열에 옮긴다해도 똑같이 swap을 이상하게 해야하는 경우가 발생했다.

 

다음은 List로 관리하는 것이다. 꼭 객체 배열이 필요한게 아닌 모든 미생물 객체를 List에 넣는 것이다.

맨 처음에 모든 값을 움직이고 가장자리에 닿았는지, 닿았다면 방향이 바뀌고 미생물의 값을 반으로 나눈다.

다음으로 생각한 건 정렬이다. 양이 많은 것을 기준으로 방향을 정한다고 하니 크기가 큰 순서대로 정렬 후 방향을 정하는 것이다.

 

만약 비교할 때 x, y 좌표가 같다면 2개를 단순히 합쳐주고 작은 양을 가진 객체는 없애주면 된다.

2. 구현

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


class Virus implements Comparable<Virus> {
    int height, width, amount, dir;

    Virus(int height, int width, int amount, int dir) {
        this.height = height;
        this.width = width;
        this.amount = amount;
        this.dir = dir;
    }

    public void changeDir() {
        switch (this.dir) {
            case 1: {
                this.dir = 2;
                break;
            }
            case 2: {
                this.dir = 1;
                break;
            }
            case 3: {
                this.dir = 4;
                break;
            }
            case 4: {
                this.dir = 3;
                break;
            }
        }
    }

    @Override
    public int compareTo(Virus o) {
        return o.amount - this.amount;
    }
}

public class Solution {

    static int N, M, K;
    static ArrayList<Virus> list = new ArrayList<>();
    static int[] dx = {0, 0, 0, -1, 1};
    static int[] dy = {0, -1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int height = Integer.parseInt(st.nextToken());
                int width = Integer.parseInt(st.nextToken());
                int amount = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());

                list.add(new Virus(height, width, amount, dir));
            }

            for (int i = 0; i < M; i++) {
                move();
            }

            int answer = 0;
            for(int i = 0; i<list.size(); i++){
                answer += list.get(i).amount;
            }
            list.clear();
            System.out.println("#" + c + " " + answer);
        }
    }

    static void move() {
        for (int i = 0; i < list.size(); i++) {
            Virus v = list.get(i);
            v.height = v.height + dy[v.dir];
            v.width = v.width + dx[v.dir];

            if (v.width == 0 || v.height == 0 || v.width == N - 1 || v.height == N - 1) {
                v.changeDir();
                v.amount = v.amount / 2;
                if (v.amount == 0) {
                    list.remove(i);
                    i--;
                }
            }
        }
        Collections.sort(list);

        for (int i = 0; i < list.size() - 1; i++) {
            Virus c = list.get(i);
            for (int j = i + 1; j < list.size(); j++) {
                Virus n = list.get(j);
                if(n.height == c.height && n.width == c.width){
                    c.amount = c.amount + n.amount;
                    list.remove(j);
                    j--;
                }
            }
        }
    }
}

compare하는 부분과 방향을 야바꾸는 것을 클래스 내부에서 구현했다.

move의 2번째 for문에서 1 -> 2, 3, 4를 비교, 2 -> 3, 4를 비교하며 합쳐나갔다.

3. 마무리

처음 접근을 이상하게 했더니 답이 나오지 않았다.

BFS, DFS는 완탐인데 여기서 완탐을 할 필요가 없었고 단순 시뮬레이션 문제임을 알았다.