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

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

SW Expert Academy

---

1. 문제 요약

1. 가장자리 셀 도착 시

  -> 군집 내 미생물 절반으로 감소, 절반이 1보다 작을 경우 사라짐

  -> 이동방향 반대

2. 여러 군집이 한군데 모일 경우

  -> 미생물 수 합침

  -> 이동방향은 미생물 수가 가장 많은 군집의 방향을 따라감

 

2. 풀이

시뮬레이션 문제이다. 아기상어, 낚시왕, 미생물 격리는 서로 비슷한 문제들이다.

우선순위 큐를 이용해서 풀었다.

정렬조건은 미생물 수 많은 순으로 정렬해주었다.

이동하기 전, pq에서 좌표를 하나씩 꺼내어 목표 좌표에 따라 달라질 값들을  이동시킬 큐 move_q에 넣어준다.

이동하기 위해 move_q의 값들을 하나씩 꺼내서 map에 세팅해준다.

다시 map을 보면서 null이 아닌 좌표는 pq에 넣어준다.

 

우선순위 큐를 2개 써서 메모리가 남들보다 2배는 더 많이 나왔다.

대부분 list로 많이 풀더라. 나도 list로 다시 풀어봐야 겠다.

그리고 이거 풀면서 새롭게 알게된 점이 있다.

우선순위큐(PriorityQueue) 쓰는데 정렬 조건 안주면 런타임에러가 난다!

 

3. 코드

리스트 사용

 

 

우선순위 큐 사용

import java.io.*;
import java.util.*;
 
public class SW_2382_미생물격리 {
 
    static int N, M, K, ans;
    static Pos[][] map;
    static PriorityQueue<Pos> pq; //미생물 수 많은 순으로 정렬
    static PriorityQueue<Pos> move_q;
     
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
     
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int 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());
            map = new Pos[N][N];
            pq = new PriorityQueue<> (); 
            for (int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
                int y = Integer.parseInt(st.nextToken());
                int x = Integer.parseInt(st.nextToken());
                int cnt = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken())-1;
                pq.offer(new Pos(y, x, cnt, dir));
                map[y][x] = new Pos(y, x, cnt, dir);
            } //입력 끝
             
            ans = 0;
            solution();
            System.out.println("#"+tc+" "+ans);
        }
    }
     
    static void solution() {
        for (int time=0; time<M; time++) {
            if (time>0) getCell(); //null이 아니면 pq에 넣어줌
            move(); //이동
        }
         
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (map[i][j] ==null) continue;
                ans += map[i][j].cnt;
            }
        }
    }
     
    static void move() {
        move_q = new PriorityQueue<> ();
        while (!pq.isEmpty()) {
            Pos cur = pq.poll();
            int y = cur.y;
            int x = cur.x;
            int cnt = cur.cnt;
            int d = cur.dir;
            map[y][x] = null;
             
            int ny = cur.y+dy[d];
            int nx = cur.x+dx[d];
            if (ny==0 || ny==N-1 || nx==0 || nx==N-1) { //가장자리일 때
                if (cnt/2 >= 1) {
                    int nd=0;
                    switch (d) {
                    case 0: nd=1; break;
                    case 1: nd=0; break;
                    case 2: nd=3; break;
                    case 3: nd=2; break;
                    }
                    move_q.offer(new Pos(ny, nx, cnt/2, nd));
                }
            } else {
                move_q.offer(new Pos(ny, nx, cnt, d));
            }
        }
         
        while (!move_q.isEmpty()) {
            Pos cur = move_q.poll();
            int y = cur.y;
            int x = cur.x;
            int cnt = cur.cnt;
            int d = cur.dir;
             
            if (map[y][x] != null) {
                map[y][x].cnt += cnt; //미생물 수만 더해줌
                 
            } else {
                map[y][x] = cur;
            }
        }
    }
     
    static void getCell() {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (map[i][j] ==null) continue;
                pq.offer(map[i][j]);
            }
        }
    }
     
     
    static class Pos implements Comparable<Pos>{
        int y, x, cnt, dir;
        Pos(int y, int x, int cnt, int dir) {
            this.y = y;
            this.x = x;
            this.cnt = cnt;
            this.dir = dir;
        }
        @Override
        public int compareTo(Pos o) {
            if (o.cnt - this.cnt == 0) {
                if (this.y - o.y == 0) {
                    return this.x - o.x;
                }
                else return this.y - o.y;
            }
            else return o.cnt - this.cnt;
        }
    }
}

4. 사담