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

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

문제정리

1. 가장 바깥쪽 가장자리 부분에 위치한 셀들에는 특수한 약품이 칠해져 있다.

2. 최초 각 미생물 군집의 위치와 군집 내 미생물의 수 , 이동 방향이 주어진다.

약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상 , 하 , 좌 , 우 이다.

3. 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.

4. 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면 군집 내 미생물의 절반이 죽고,

이동방향이 반대로 바뀐다.

5. 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.

합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중

미생물 수가 가장 많은 군집의 이동방향이 된다. 합쳐지는 군집의 미생물 수가 같은 경우는

주어지지 않는다.

6. M 시간 동안 미생물 군집들을 격리하였다. M시간 후 남아 있는 미생물 수의 총합을 구하여라.

문제issue

1. 미생물이 동시에 이동 후 크기에 따라서 dir 결정

- 낚시왕 문제와 비슷한 방법으로 해결한다.

해결흐름

1. 미생물 정보(r, c, 미생물의 수, 이동 방향)을 list에 저장한다.

2. list에서 미생물을 꺼내서 이동한다.

3. 미생물 군집이 만나는 셀의 경우는 다음과 같다.

(1) 아무것도 없음

(2) 약품

(3) 다른 군집이 있음

4. list상에서 모든 움직임을 끝낸 후 미생물의 수를 나타내는 size[][] 와

미생물의 합 sum[][] , 이동 방향을 나타내는 dir[][]을 생성한다.

5. list에서 군집을 꺼내서 size와 dir에 넣어주고 경우에 따라 sum에 미생물 수 의 합을 넣어준다.

(1) 아무것도 없는 경우 그냥 넣는다. sum에는 누적을 해준다.

(2) 뭔가 있는 경우 size를 비교해서 지금 넣으려는게 클 경우에만

size와 dir를 갱신해준다. sum에는 누적을 해준다.

(3) list를 다 돌고 list를 다시 선언해준다. sum[][]과 dir[][]을 list에 다시 넣어준다.

6. M초가 끝난뒤 list에 있는 군집을 합해서 출력한다.

소스코드

xxxxxxxxxx
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
​
public class Solution {
​
    static class micro {
        int r;
        int c;
        int number;
        int dir;
​
        public micro(int r, int c, int number, int dir) {
            super();
            this.r = r;
            this.c = c;
            this.number = number;
            this.dir = dir;
        }
    }
​
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            List<micro> list = new ArrayList<micro>();
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine().trim());
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int number = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());
                list.add(new micro(r, c, number, dir));
            }
​
            int[] dr = { 0, -1, 1, 0, 0 }; // x,상,하,좌,우
            int[] dc = { 0, 0, 0, -1, 1 };
            for (int i = 0; i < M; i++) {
                // M초동안 이동
                for (int j = 0; j < list.size(); j++) {
                    int r = list.get(j).r;
                    int c = list.get(j).c;
                    int number = list.get(j).number;
                    int dir = list.get(j).dir;
                    int nr = r + dr[dir];
                    int nc = c + dc[dir];
                    // list에서 미생물을 꺼내 이동하여 list에 갱신해준다. 약품인 경우는 number /= 2 , dir도 갱신
                    if (nr <= 0 || nr >= N-1 || nc <= 0 || nc >= N-1) {
                        number /= 2;
                        if(dir == 1) dir = 2;
                        else if(dir == 2) dir = 1;
                        else if(dir == 3) dir = 4;
                        else if(dir == 4) dir = 3;
                    }
                    list.get(j).r = nr;
                    list.get(j).c = nc;
                    list.get(j).number = number;
                    list.get(j).dir = dir;
                }
                // n_map[][] , d_map[][] , d_map[][]
                int[][] n_map = new int[N][N];
                int[][] d_map = new int[N][N];
                int[][] s_map = new int[N][N];
                for (int j = 0; j < list.size(); j++) {
                    int r = list.get(j).r;
                    int c = list.get(j).c;
                    int number = list.get(j).number;
                    int dir = list.get(j).dir;
                    if(n_map[r][c] == 0) {
                        n_map[r][c] = number;
                        d_map[r][c] = dir;
                        s_map[r][c] += number;
                    } else if(n_map[r][c] < number) {
                        n_map[r][c] = number;
                        d_map[r][c] = dir;
                        s_map[r][c] += number;
                    } else {
                        s_map[r][c] += number;
                    }
                }
                list = new ArrayList<micro>();
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < N; k++) {
                        if(s_map[j][k] != 0) {
                            list.add(new micro(j,k,s_map[j][k],d_map[j][k]));
                        }
                    }
                }
            }
            int result = 0;
            for (int i = 0; i < list.size(); i++) {
                result += list.get(i).number;
            }
            System.out.println("#" + tc + " " + result);
        } // end of tc
    } // end of main
} // end of class