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

Kyungmin·2024년 2월 21일

구현 알고리즘 자바

JAVA알고리즘

목록 보기

20/23

📝 문제

📎 백준 17144 미세먼지 안녕!

✅ 문제조건

공기청정기 는 항상 1번 열 에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
확산되는 양은 Ar,c/5 이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
(r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.

공기청정기가 작동한다.

공기청정기에서는 바람이 나온다.
위쪽 공기청정기의 바람은 반시계방향 으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향 으로 순환한다.
바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
공기청정기에서 부는 바람은 미세먼지가 없는 바람 이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

< JAVA 코드 >

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

public class Baek_17144 {

    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static int[][] box;
    static int head, foot;
    static int r,c,t;

    static int[][] dust() {
        int[][] copymap = new int[r][c];

        copymap[head][0] = -1;
        copymap[foot][0] = -1;

        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(box[i][j] > 0) {
                    copymap[i][j] += box[i][j];
                    for(int k=0; k<4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if(nx>=0 && nx<r && ny>=0 && ny<c && box[nx][ny] != -1) {
                            copymap[nx][ny] += (box[i][j] / 5);
                            copymap[i][j] -= (box[i][j] / 5);
                        }
                    }
                }
            }
        }   // end for
        return copymap;
    }

    static void airup() {
        for(int i= head-1; i>0; i--) {
            box[i][0] = box[i-1][0];
        }
        for(int i=0; i<c-1; i++){
            box[0][i] = box[0][i+1];
        }
        for(int i=0; i<head; i++) {
            box[i][c-1] = box[i+1][c-1];
        }
        for(int i = c-1; i>1; i--) {
            box[head][i] = box[head][i-1];
        }

        box[head][1] = 0;
    }

    static void airdown() {
        for (int x = foot + 1; x < r - 1; x++) {
            box[x][0] = box[x + 1][0];
        }
        for (int y = 0; y < c - 1; y++) {
            box[r - 1][y] = box[r - 1][y + 1];
        }
        for (int x = r - 1; x > foot; x--) {
            box[x][c - 1] = box[x - 1][c - 1];
        }
        for (int y = c - 1; y > 1; y--) {
            box[foot][y] = box[foot][y - 1];
        }

        box[foot][1] = 0;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        box = new int[r][c];    // 7 x 8
        for(int i=0; i<r; i++) {
            st = new StringTokenizer(bf.readLine());
            for(int j=0; j<c; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i=0; i<r; i++) {
            if(box[i][0] == -1) {
                head = i;
                foot = i + 1;
                break;
            }
        }

        for(int i=0; i<t; i++) {
            box = dust();
            airup();
            airdown();
        }
        int sum = 2;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                sum += box[i][j];
            }
        }
        System.out.println(sum);
    }
}

✅ 풀이 방법

먼저 미세먼지가 퍼져나가는 과정이 끝나고 난 후의 배열이 필요하다고 생각했다. dust() 라는 함수를 만들고 원본배열(box) 에서 문제의 조건에 따라 변경되는 값 들을 업데이트 해줄 배열 이 필요했고 copymap 이라는 배열에 그 값들을 저장했다.

✍️ 핵심 알고리즘

1️⃣ dust() 함수 - 미세먼지 퍼짐

 for(int i=0; i<r; i++) {
      for(int j=0; j<c; j++) {
          if(box[i][j] > 0) {
              copymap[i][j] += box[i][j];
                  for(int k=0; k<4; k++) {
                     int nx = i + dx[k];
                     int ny = j + dy[k];
                       if(nx>=0 && nx<r && ny>=0 && ny<c && box[nx][ny] != -1) {
                            copymap[nx][ny] += (box[i][j] / 5);
                            copymap[i][j] -= (box[i][j] / 5);
                        }
                    }
                }
            }
        }   // end for

이 부분이 미세먼지가 퍼져나가는 과정에서 가장 중요하다고 느꼈고 머리로 알지만 실제 구현하는데 있어 많은 시간을 허비한 부분이다.

0 30 7
0 10 0
0 0 0

이라는 원본 map 이라는 배열이 있다고 해보자.
먼저 배열의 값이 0보다 크다 면 미세먼지가 존재 한다는 말과 같다.
따라서 내가 값을 업데이트 하려는 새로운배열(copymap) 에 해당 값(예를 들어 위 예시 배열에서 30 이라고 하자) 을 저장한다.

0 30 0
0 0 0
0 0 0

그러면 copymap 의 배열 상태는 위와 같게 된다. 여기서 이제 해당 값 기준으로 상하좌우를 살펴 인덱스범위조건과 -1이 아니라면 밑의 과정

copymap[nx][ny] += (box[i][j] / 5);
copymap[i][j] -= (box[i][j] / 5);

을 통해서 copymap[nx][ny] 에 box[i][j] / 5 를 더해준다. 즉 예시로 보면 30/5 = 6 을 더하는것과 같다. ( 아직 오른쪽만 했을 때)

0 30 6
0 0 0
0 0 0

그렇게 된다면 다음과 같이 copymap 이 업데이트 될 것이고, 이제 copymap[i][j] -= (box[i][j] / 5); , 즉 업데이트가 되어야 할 copymap 배열의 [i][j] 의 값, 즉 예시로는 30에서 box[i][j] / 5 값을 뺴준다. 굳이 방향의 개수를 계산해서 "값 x 방향" 을 안해줘도 되는 이유는 갈 수 있는 방향만 간다음 값이 바뀌기 때문에 굳이 "값 x 방향" 으로 처리해주지 않았다.

처음에 copymap을 깊은 복사로 box 을 복사하여 사용하려 했었다. 하지만 그렇게 된다면 값이 업데이트되면서 중복되는 값들이 생기고, 결과가 달라지게 된다. 따라서 copymap 을 사용할 때 초기화만 해준 후, 조건에 만족할 때마다 box 배열에서 값을 가져왔다.

2️⃣ airup() 함수 - 공기 청정기 순환

static void airup() {
        for(int i= head-1; i>0; i--) {
            box[i][0] = box[i-1][0];
        }
        for(int i=0; i<c-1; i++){
            box[0][i] = box[0][i+1];
        }
        for(int i=0; i<head; i++) {
            box[i][c-1] = box[i+1][c-1];
        }
        for(int i = c-1; i>1; i--) {
            box[head][i] = box[head][i-1];
        }

        box[head][1] = 0;
    }

이 부분은 문제에서 언급한 위쪽 공기청정기 의 작동을 표현한 코드이다.
여기서 주목해야 할 부분은 다음과 같다.

위쪽 공기청정기의 바람은 반시계 방향으로 분다.
공기청정기에서 부는 바람은 미세먼지가 없다.

1. 위쪽 공기청정기의 바람은 반시계 방향으로 분다.

먼저 1번을 살펴보자.
만약 먼저 오른쪽으로 부는 바람만을 생각했을 때, 바람이 반시계 방향으로 분다해서 단순히 왼쪽에 있는 배열의 값을 바람이 부는 방향인 오른쪽으로 업데이트해주면 될까?
그렇지 않다. 그렇게 되면 왼쪽-> 오른쪽 으로 값이 변경되면서 순차적으로 원하지 않는 업데이트된 값 들이 오른쪽에 저장 되게 된다.
따라서 반대방향인 시계방향으로, 즉 역 으로 값들을 땡겨오면서 업데이트하게되면 원하는 값을 얻을 수 있다.

airdown() 의 방향만 반대고 원리는 같으므로 생략한다.