[백준] Q17144 미세먼지, 안녕! JAVA

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

17144번: 미세먼지 안녕!

 

1. 문제의 이해 및 유형

구현, simulation , 2차원 배열 순회(시계방향 테두리)

 

R $*$ C인 격자판에서 공기청정기 위치가 주어지고, T초 뒤의 상황을 구하는 문제이다.

문제에서 주어진 알고리즘 그대로 구현해내는 문제이다.

 

2. 문제  접근 방식

문제에 주어진 대로 구현하면 되는 것을 안 후에, 구현을 위해 필요한 것을 생각했다.1. 공기청정기의 위치. ([a,0], [b,0])2. 확산 및 공기청정기 작동 순서 고려하기.  2-1. 처음에 확산이 우선 되어야한다.    a. 확산되어야 하는 먼지의 위치를 어떻게 알까?       2차원 배열을 모두 보는 방법 또는 처음에 Queue에 모두 등록하는 방법    b. 확산을 할 때, 확산의 영향이 이후의 계산에 영향을 끼치면 안된다.    c. [5] [14] 에서 5 -> 14 순으로 계산할 때 고려하지 않는다면         [7][12]가 되는데, [4][1] + [2][12] => [6][13]이 올바른 값이다.    d. 영향을 주지 않도록 map을 하나 더 만들어 갱신하는 식으로 하면 될것 같다.  2-2. 확산된 map에서 공기청정기 위치를 활용하여 rotate한다.    2차원 배열 순회 방식.

 

작동 순서는 문제에 주어진 그대로 구현하되, 필요한 자료를 잘 정리하는 것에 중점을 두었다.

1. Queue에 먼지를 넣어두고, 꺼내면서 모든 먼지를 확산을 시킨다. (newMap에 갱신시키고 map에 update한다)

2. 이후 rotate를 한다.(이것도 당기는 방식 또는 미는 방식이 있을 수 있다, 순회 관점또는 접근 방법 차이)

3. 새로운 작업을 위해 map을 돌면서 새로운 먼지들을 queue에 등록한다.

/*
2022.01.07

이름 및 난이도 : 미세먼지 안녕! Gold IV samsung 
문제이해 
-----------------
 공기청정기는 항상 1번열
- 동작과정
    1. 미세먼지 확산 
        - 인접한 네 방향으로 확산
        - 확산되는 양은 A/5
        - 남은 먼지는 A - (A/5)* 확산된 방향
         ** 순서에 상관이 없어야 하지만 각각의 먼지가 분산되는 과정에서 영향을 줄 수 있다.
         ** 영향을 주지 않게 하기 위해 상태를 따로 저장해야한다.
           > 1-1 새로운 Map을 생성하여 반영하는 방법  >> 2차원 배열
           > 1-2 새로운 List를 생성하여 반영하는 방법. >> arrayList(but, 안에 많이 들어감)
    2. 공기청정기 작동
        - 위쪽은 반 시계 방향
        - 아래쪽은 시계방향.

접근 방법 :
제한 조건 : 
*/

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

public class Q17144_Review {
    static int R, C, T;
    static int[][] map;
    static int[] cleanerPosition;
    static ArrayList<Point> dustList;
    // dir 시계방향. ^ > V <
    static int[][] dir = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        cleanerPosition = new int[2]; // 0 위쪽 1 아래쪽
        dustList = new ArrayList<Point>();

        int idx = 0;
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (j == 0 && map[i][j] == -1) {
                    cleanerPosition[idx++] = i;
                } else if (map[i][j] > 0) {
                    dustList.add(new Point(i, j));
                }
            }
        }
    }

    public static void solution() {
        while (T-- > 0) {
            dustDiffusion();
           // printMap();
            doCleaner();
            //printMap();
        }
        int ans = findAnswer();
        System.out.println(ans);
    }

    public static int findAnswer() {
        int ans = 0;
        for (Point p : dustList) {
            ans += map[p.x][p.y];
        }
        return ans;
    }

    public static void dustDiffusion() {
        // 영향을 배제하기 위한 새로운 맵 생성 (feat. clenar)
        int[][] newMap = new int[R][C];
        newMap[cleanerPosition[0]][0] = -1;
        newMap[cleanerPosition[1]][0] = -1;

        // 가지고 있는 dust들에 대해 확산시킴.
        for (Point cur : dustList) {
            // 5보다 낮으면 영향 X
            if (map[cur.x][cur.y] < 5) {
                newMap[cur.x][cur.y] += map[cur.x][cur.y];
                continue;
            }
            int cnt = 0;
            int diffuseSize = map[cur.x][cur.y] / 5;
            for (int i = 0; i < 4; i++) {
                int nx = dir[i][0] + cur.x;
                int ny = dir[i][1] + cur.y;
                if (nx < 0 || ny < 0 || nx > R - 1 || ny > C - 1)
                    continue;
                if (map[nx][ny] == -1)
                    continue;
                newMap[nx][ny] += diffuseSize;
                cnt++;
            }
            newMap[cur.x][cur.y] += map[cur.x][cur.y] - cnt * diffuseSize;
        }

        // map Update
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = newMap[i][j];
            }
        }
    }

    // 빨아들이는 느낌으로 간다. swap과 같은 과정이 필요 없기 때문.
    public static void doCleaner() {
        // 위방향
        int x = cleanerPosition[0] - 1;
        int y = 0;
        int d = 0;
        int offset = 1;
        int nx = -1;
        int ny = -1;
        while (true) {
            // 다음 칸 찾기.
            while (true) {
                nx = x + dir[d][0];
                ny = y + dir[d][1];
                if (nx < 0 || ny < 0 || nx > cleanerPosition[1] - 1 || ny > C - 1)
                    d = (d + offset) % 4;
                else
                    break;
            }
            if (map[nx][ny] == -1) {
                map[x][y] = 0;
                break;
            }
            map[x][y] = map[nx][ny];
            x = nx;
            y = ny;
        }

        // printMap();
        // 아래쪽 (아래 오른쪽 위쪽 왼쪽)
        x = cleanerPosition[1] + 1;
        y = 0;
        d = 2;
        offset = 3;

        while (true) {
            while (true) {
                nx = x + dir[d][0];
                ny = y + dir[d][1];
                if (nx < cleanerPosition[1] || ny < 0 || nx > R - 1 || ny > C - 1)
                    d = (d + offset) % 4;
                else
                    break;
            }
            if (map[nx][ny] == -1) {
                map[x][y] = 0;
                break;
            }
            map[x][y] = map[nx][ny];
            x = nx;
            y = ny;
        }
        // 새로운 미세먼지 Lis t생 성
        dustList = new ArrayList<Point>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] > 0) {
                    dustList.add(new Point(i, j));
                }
            }
        }
    }

    public static void printMap() {
        System.out.println();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static class Point {
        int x, y;

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

 

3. 배운 점

2차원 배열 순회 방법

 - 여러 코드들을 보았을 때 따로따로 시계방향에 따라 범위를 주고 돌리는 방법(4개의 for문)

 - 이전에 달팽이 순회방법 코드를 본 것이 기억나 while문에서 방향만 바꾸어주는 방법 등을 사용하였다.

 

앞의 계산이 영향을 준다면 새로운 저장공간을 사용할 수 있다.