[BOJ - JAVA] 17144 - 미세먼지 안녕! (시뮬레이션)

# 주소

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Point{
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class Main{
    static int n, m, t;
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int[][] arr;
    static int[][] ans;
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        t = scan.nextInt();
        arr = new int[n][m];
        ans = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = scan.nextInt();
                if(arr[i][j] == -1)
                    queue.offer(new Point(i, j));
            }
        }
        while(t--> 0){
            move();
            ans = new int[n][m];
            clean();
        }
        int answer = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(arr[i][j] > 0)
                    answer += arr[i][j];
        System.out.println(answer);
    }
    static void move(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] > 0){
                    check(i,j);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] += ans[i][j];
            }
        }
    }
    static void check(int x, int y){
        int count = 0;
        for(int i = 0; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if(arr[nx][ny] == -1)
                continue;
            count++;
            ans[nx][ny] += arr[x][y] / 5;
        }
        arr[x][y] -= (arr[x][y] / 5) * count;
    }
    static void clean(){
        Point now = queue.poll();
        for(int i = now.x - 1; i > 0; i--)
            arr[i][0] = arr[i - 1][0];
        for(int i = 0; i < m - 1; i++)
            arr[0][i] = arr[0][i + 1];
        for(int i = 0; i < now.x; i++)
            arr[i][m - 1] = arr[i + 1][m - 1];
        for(int i = m - 1; i > 1; i--)
            arr[now.x][i] = arr[now.x][i - 1];
        arr[now.x][1] = 0;
        Point now2 = queue.poll();
        for (int i = now2.x + 1; i < n - 1; i++)
            arr[i][0] = arr[i + 1][0];
        for (int i = 0; i < m - 1; i++)
            arr[n - 1][i] = arr[n - 1][i + 1];
        for(int i = n - 1; i > now2.x; i--)
            arr[i][m - 1] = arr[i - 1][m - 1];
        for(int i = m - 1; i > 1; i--)
            arr[now2.x][i] = arr[now2.x][i - 1];
        arr[now2.x][1] = 0;
        queue.offer(new Point(now.x, now.y));
        queue.offer(new Point(now2.x, now2.y));
    }
}

시뮬레이션 문제를 이제부터 풀어보려고 합니다.

시뮬레이션 문제는 대체로 난이도가 어려운 것 같습니다.

생각해야할 부분도 많고 문제를 아무리 읽어도 이해가 안되는 부분이 참 많은 것 같아요.

그리고 상황에 따라 어떤 자료구조를 사용해야 할지나 어떤 알고리즘 기법을 써서 풀어야할지 막막한 경우도 많습니다.

옛날에 수능 국어를 기준으로 생각해보면 비문학 문제를 푸는 느낌이랄까요 ....

어떤 누구의 코드 참조 없이 혼자서 생각해서 푼 문제이니 풀이가 지저분하더라도 봐주시면 감사하겠습니다.

 

lass Main{
    static int n, m, t;
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int[][] arr;
    static int[][] ans;
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        t = scan.nextInt();
        arr = new int[n][m];
        ans = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = scan.nextInt();
                if(arr[i][j] == -1)
                    queue.offer(new Point(i, j));
            }
        }

n, m, t를 입력받고 arr와 ans배열을 n x m크기로 생성하겠습니다.

arr는 실제 미세먼지가 들어간 배열이고 ans배열은 주변 4방향으로 퍼졌을 때를 담을 tempary배열입니다.

이중 for문으로 arr를 모두 저장하고 arr가 -1이면 queue에도 담을 것입니다.

이 -1이 들어간 곳이 청소기가 있는 곳이 되겠습니다.

청소기의 역할은 들어오는 미세먼지를 모두 빨아들입니다.

 while(t--> 0){
            move();
            ans = new int[n][m];
            clean();
        }

그리고 제한된 시간동안 t를 감소하여 move함수를 실행하며 ans를 초기화 하겠습니다.

static void move(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j] > 0){
                    check(i,j);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] += ans[i][j];
            }
        }
    }

move함수는 다음과 같습니다.

n x m번 동안 arr값이 0보다 클 때 check()함수를 실행하고 arr에다가는 담아온 ans배열을 더해줍니다.

그럼 check()함수를 알아봐야겠죠?

static void check(int x, int y){
        int count = 0;
        for(int i = 0; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if(arr[nx][ny] == -1)
                continue;
            count++;
            ans[nx][ny] += arr[x][y] / 5;
        }
        arr[x][y] -= (arr[x][y] / 5) * count;
    }

다음과 같습니다.

4가지 방향에 대해 인덱스의 크기를 벗어나면 continue해주시고 -1일 때도 continue합니다.

그리고 그렇지 않을 경우 count++한 후 ans에는 arr의 크기를 5로 나눈 몫을 더해줍니다.

그리고 arr에는 각각 퍼질 수 있는 인덱스에 대해 더해주었던 count를 곱한 것을 arr에서 감소시켜줍니다.

이렇게 되면 check에는 감소한 arr값이 남는 것입니다.

그리고 청소기를 통해 기류가 움직인 후의 미세먼지도 알아봐야겠죠? 

clean함수를 살펴봅시다.

static void clean(){
        Point now = queue.poll();
        for(int i = now.x - 1; i > 0; i--)
            arr[i][0] = arr[i - 1][0];
        for(int i = 0; i < m - 1; i++)
            arr[0][i] = arr[0][i + 1];
        for(int i = 0; i < now.x; i++)
            arr[i][m - 1] = arr[i + 1][m - 1];
        for(int i = m - 1; i > 1; i--)
            arr[now.x][i] = arr[now.x][i - 1];
        arr[now.x][1] = 0;
        Point now2 = queue.poll();
        for (int i = now2.x + 1; i < n - 1; i++)
            arr[i][0] = arr[i + 1][0];
        for (int i = 0; i < m - 1; i++)
            arr[n - 1][i] = arr[n - 1][i + 1];
        for(int i = n - 1; i > now2.x; i--)
            arr[i][m - 1] = arr[i - 1][m - 1];
        for(int i = m - 1; i > 1; i--)
            arr[now2.x][i] = arr[now2.x][i - 1];
        arr[now2.x][1] = 0;
        queue.offer(new Point(now.x, now.y));
        queue.offer(new Point(now2.x, now2.y));

좀 지저분합니다..

하나로 통합하여 사용할 수 있는데 그냥 깔끔하게 어짜피 청소기는 2개밖에 없으니 전부 for문으로 나타내자 싶어서 이렇게 했습니다.. ㅠ

각각의 청소기의 위치에 따라 옆으로 옮기거나 위로 미세먼지를 옮긴 후 마지막에 queue에 now와 now2를 담습니다.

이 모든 것을 t번동안 반복한 후 answer에 모든 arr값을 더해주어 출력하시면 정답이 됩니다.

clean함수를 더 간단하게 할 수 있으신 분은 알려주십시오...

감사합니다.