[SWEA-java] 미생물 격리

알고리즘 : 시뮬레이션

---

문제 설명

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

 

---

🪟내 풀이

 

삼성식 시뮬레이션 문제이다.
물론 실제 삼성전자 코테를 이번 하반기에 가서 본 입장으로선 그것보다는 귀여운 수준의 문제지만
생각지도 못한 실수를 해서 고생했다.

내가 한 실수는 set에 자표를 저장하고 사용할 때
split으로 나눠서 쓰는게 아니라 단순하게 charAt한다음 - '0'해서 사용한 것이다.
이렇게 사용하면 당연히 안되는 게, 좌표 크기가 2자리 수가 되면 사고가 나는 것이다.

어이없는 실수를 했고, 이어서 내가 푼 방식을 순서로 설명하고자 한다.

1. 초기화

• 새로운 클래스 Virus를 생성해서 좌표/방향성/미생물 수 를 저장한다.
• dist배열을 3차원으로 선언해서 4가지 방향성에 대한 값을 저장한다.
  • 이렇게 저장한 이유는 단순하게 1번씩 방향으로 군집을 이동시킨 다음, 겹칠 경우 방향성이 다른 쪽에서 오는 것이므로 한 위치에 여러가지 방향성이 오는 것을 저장하고, 4번을 순회하면서 제일 큰값의 방향성을 기준으로 더한 합을 새롭게 갱신하기 위함이다.
• dx,dy 배열로 상,하,좌,우 순서를 저장한다, -> 따로 저장할때는 1로 빼서 저장 입력값이 1,2,3,4이므로
• Virus를 저장할 큐를 생성 -> 움직임을 위해
• HashSet으로 String을 저장하는 데 좌표를 저장한다 "1-2"이런식으로 저장해 중복을 막는다

2. 각자의 방향성으로 이동

• 약품이 뿌려진 위치로 이동하면, 방향성을 바꾸고 /2를 진행 후 dist에 저장
• 약품이 아닌 곳이면, 방향성 유지 및 현재 미생물 수를 dist에 저장

3. 결산

• 위에서 설명한 대로 set을 이용해서 결산을 진행한다.
• 결국 최종적으론 큐에는 맨 마지막의 Virus들이 위치함으로 순회하면서 sum을 더한다.

package example;

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

public class Solution {

    static class Virus {
        int x;
        int y;
        int dir;
        int cost;

        public Virus(int x,int y,int dir,int cost ) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cost = cost;
        }
    }
    private static int[][][] dist;
    private static int T;
    private static ArrayDeque<Virus> q;
    private static HashSet<String> locset;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};
    private static int N,M,K;

    private static boolean isKill(int x,int y) {
        return ( ( x == 0 ) || (x == N-1) || ( y== 0 ) || ( y== N-1 ));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 1 ; i <= T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            dist = new int[N][N][4];
            locset = new HashSet<>();
            // 큐 초기화
            q = new ArrayDeque<>();
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());

                q.offer(new Virus(x,y,dir-1,cost));
            }
            // 거리 초기화
            for (int cnt = 0; cnt < M; cnt++) {
                locset = new HashSet<>();
                dist = new int[N][N][4];
                while (!q.isEmpty()) {
                    Virus cur = q.poll();

                    int nx = cur.x + dx[cur.dir];
                    int ny = cur.y + dy[cur.dir];
                    if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                    if (isKill(nx,ny)) {
                        int newCost = cur.cost / 2;
                        int newDir = 0;
                        if(cur.dir == 0) newDir = 1;
                        else if(cur.dir == 1) newDir = 0;
                        else if(cur.dir == 2) newDir = 3;
                        else if(cur.dir == 3) newDir = 2;

                        dist[nx][ny][newDir] = newCost;
                        locset.add(""+nx+"-"+ny);

                    }else {
                        dist[nx][ny][cur.dir] = cur.cost;
                        locset.add(""+nx+"-"+ny);
                    }    
                }

                // 결산 시작 
                for (String loc : locset) {
                    String[] coords = loc.split("-");
                    int x = Integer.parseInt(coords[0]);
                    int y = Integer.parseInt(coords[1]);

                    int maxnum = 0;
                    int maxdir = 0;
                    int current = 0;
                    int sum = 0;
                    for (int next: dist[x][y]) {
                        if (maxnum < next) {
                            maxnum = next;
                            maxdir = current;
                        }
                        sum += next;
                        current++;
                    }
                    q.offer(new Virus(x, y, maxdir, sum));
                }

            }
            int retSum = 0;
            for (Virus v : q) {
                retSum += v.cost;
            }
            sb.append("#"+i+" "+retSum+"\n");

        }
        System.out.println(sb);
    }
}