SW 역량 테스트 기출 문제(미세먼지 안녕)

[미세먼지 안녕 _ 17144]

 

 

* 조건

1. 1초 동안 이루어지는 사이클은 [미세먼지 확산 -> 공기청정기 가동]이다
2. 공기청정기는 2개 -> 상단 공기청정기는 반시계방향, 하단 공기청정기는 시계방향으로 바람을 가동한다
3. T초 이후의 남아있는 미세먼지의 양을 출력한다

* 알고리즘

- 미세먼지를 인접한 곳에 확산시키기: BFS

- 공기청정기를 가동시켜 방향에 맞게 회전시키기: 시뮬레이션

 

* 로직(Logic)

- 상단, 하단 공기청정기의 위치를 담고, 미세먼지가 존재하는 위치를 큐에 담는다

- 담긴 큐를 기반으로 미세먼지를 확산시킨다

- 확산시키면서 계산된 값들을 tmp 배열에 담고, 이를 map에 다시 덮어준다

- 덮인 map을 기반으로 공기청정기를 가동한다

- 회전 방향에 맞게 배열에 있는 미세먼지 값들을 이동시킨다

- T초가 끝나면 변경된 map 배열의 미세먼지를 탐색 -> 값을 누적해 출력한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Position_17144{
    public int y, x;
    public int dir;
    public int value;

    public Position_17144(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Problem_17144 {

    static int r, c;
    static int time;
    static int[][] map;
    static int[][] tmp;

    static Queue<Position_17144> queue_dust = new LinkedList<>();   //미세먼지 큐
    static Queue<Position_17144> queue_cleaner;    //공기청정기 바람에 따라
    static Position_17144 cleaner_top;
    static Position_17144 cleaner_bottom;

    //위 오 아 왼
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int[][] directions = {
            //반시계방향(오 위 왼 아)
            {1, 0, 3, 2},
            //시계방향(오 아 왼 위)
            {1, 2, 3, 0}
    };
    static int answer = 0;

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

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        time = Integer.parseInt(st.nextToken());
        map = new int[r][c];

        int dir = 0;
        for(int i=0; i<r; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=0; j<c; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] > 0){
                    queue_dust.offer(new Position_17144(i, j));
                }
                else if(map[i][j] == -1){
                    if(dir == 0){
                        cleaner_top = new Position_17144(i, j);
                        cleaner_top.dir = dir;
                        cleaner_top.value = map[i][j];
                    }
                    else if(dir == 1){
                        cleaner_bottom = new Position_17144(i, j);
                        cleaner_bottom.dir = dir;
                        cleaner_bottom.value = map[i][j];
                    }
                    dir++;
                }
            }
        }

        //존재하는 미세먼지들을 한 사이클 퍼뜨리고 -> 새로운 맵에 누적하고 -> 그 맵을 덮어줌
        spreadDust();
        System.out.println(answer);

    }

    private static void spreadDust() {
        int count = 0;

        while (!queue_dust.isEmpty()){
            int size = queue_dust.size();
            tmp = new int[r][c];
            if(count == time){
                return;
            }

            for(int s=0; s<size; ++s){
                Position_17144 q = queue_dust.poll();

                int cnt = 0;    //미세먼지를 퍼뜨린 횟수 카운트
                int movedDust = 0;
                for(int i=0; i<4; ++i){
                    int moveY = q.y + dy[i];
                    int moveX = q.x + dx[i];

                    //맵 사이즈에 들어가고, 인접한 곳에 공기청정기가 없다면 수행
                    if(isRanged(moveY, moveX) && map[moveY][moveX] != -1){
                        movedDust = map[q.y][q.x] / 5;
                        tmp[moveY][moveX] += movedDust;

                        cnt++;
                    }
                }
                tmp[q.y][q.x] += map[q.y][q.x] - (movedDust * cnt);

            }
            count++;
            //tmp를 맵에 덮어주기
            for(int i=0; i<r; ++i){
                for(int j=0; j<c; ++j){
                    map[i][j] = tmp[i][j];
                    if(i == cleaner_top.y && j == cleaner_top.x) map[i][j] = -1;
                    if(i == cleaner_bottom.y && j == cleaner_bottom.x) map[i][j] = -1;
                }
            }

            //공기청정기 가동
            doCleaner();

            //미세먼지 위치 다시 큐에 삽입, 총 미세먼지 수 리턴
            answer = findDust();
        }
    }

    private static void doCleaner() {
        //dir = 0이면 -> 반시계방향 -> 큐에 담고 다음 인덱스값을 큐에 넣고 기존거 빼서 진행
        clean(cleaner_top);

        //dir = 1이면 -> 시계방향
        clean(cleaner_bottom);
    }

    private static void clean(Position_17144 robot) {
        queue_cleaner = new LinkedList<>();

		//공기청정기의 오른쪽부터 시작이 되기때문에 해당 칸의 정보를 큐에 삽입
        int tmpY = robot.y;
        int tmpX = robot.x + 1;
        Position_17144 start = new Position_17144(tmpY, tmpX);
        start.value = map[tmpY][tmpX];
        start.dir = robot.dir;
        map[tmpY][tmpX] = 0;
        queue_cleaner.offer(start);

        int index = 0;
        while (true){
            Position_17144 q = queue_cleaner.poll();

            int moveY = q.y + dy[directions[q.dir][index]];
            int moveX = q.x + dx[directions[q.dir][index]];

            //범위를 벗어나면 큐에 다시 넣어주고 방향 전환
            if(!isRanged(moveY, moveX)){
                Position_17144 cleaner = new Position_17144(q.y, q.x);
                cleaner.dir = q.dir;
                cleaner.value = q.value;
                queue_cleaner.offer(cleaner);

                index++;
                continue;
            }
            
            //다음 칸의 정보를 일단 저장해놓고
            Position_17144 nextCell = new Position_17144(moveY, moveX);
            nextCell.dir = q.dir;
            nextCell.value = map[moveY][moveX];

			//다음 칸이 공기청정기라면 리턴
            if(moveY == robot.y && moveX == robot.x){
                return;
            }
            //아니라면 다음 칸의 정보를 큐에 넣고, 기존 큐에 있던 값을 다음 칸 위치에 삽입
            else{
                queue_cleaner.offer(nextCell);
                map[moveY][moveX] = q.value;
            }
        }
    }

    private static int findDust() {
        queue_dust = new LinkedList<>();
        int acc = 0;
        for(int i=0; i<r; ++i){
            for(int j=0; j<c; ++j){
                if(map[i][j] > 0){
                    queue_dust.offer(new Position_17144(i, j));
                    acc += map[i][j];
                }
            }
        }
        return acc;
    }

    private static boolean isRanged(int y, int x) {
        if(y>=0 && y<r && x>=0 && x<c) return true;
        return false;
    }
}