[BOJ] 17144 미세먼지 안녕! - JAVA

1. 문제

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

17144번: 미세먼지 안녕!

이 문제는 링크에 있는 설명보다 더 자세하거나 첨언할 게 없다. 그냥 그대로다. 

적힌 모든 것들을 신경 쓰면서 풀어야 한다.

---

2. 풀이

메인

• 공기 청정기가 어떤 행에 있는지 위아래로 나눠서 변수에 저장했다. 
• 마지막으로 저장되는 공기청정기가 아래에 있는 것이므로 위의 있는 공기청정기는 아래에서 -1 해서 구했다.
• 1초마다 먼지가 확산되고->공기청정기가 위아래로 한 번씩 돌아간다. 현재 있는 먼지-공기청정기로 없어진 먼지로 계산해서 count를 출력했다.

static int R, C, T;                //크기,시간
static int[][] house;        //집
static int cleanU, cleanD;    //공기청정기 행 저장
static int[][] deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};    //시계방향

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

   R = Integer.parseInt(st.nextToken());
   C = Integer.parseInt(st.nextToken());
   T = Integer.parseInt(st.nextToken());
   house = new int[R][C];

   for (int r = 0; r < R; r++) {
      st = new StringTokenizer(in.readLine());
      for (int c = 0; c < C; c++) {
         house[r][c] = Integer.parseInt(st.nextToken());
         if (house[r][c] == -1) cleanD = r;
      }
   }
   cleanU = cleanD - 1;

   int count = 0;
   while (--T >= 0) count = spreadDust() - blowWind(true) - blowWind(false);
   System.out.println(count);

}

 

범위 체크 메서드

• 범위에 벗어나거나 공기청정기 위치라면 false를 반환한다.

private static boolean valid(int r, int c) {
   return r >= 0 && c >= 0 && r < R && c < C && !(r == cleanU && c == 0) && !(r == cleanD && c == 0);
}

 

먼지를 확산시키는 메서드

• 새 배열을 만들어서 먼지를 새로 저장한 뒤 원래 house배열을 교체했다. 원본이 남아있어야 얼마나 확산시켜야 하는지 알 수 있기 때문이다.
• 한 칸씩 탐색하면서 먼지가 없다면 다음 칸으로 넘어간다.
  • 원래의 먼지를 저장하고, 5로 나눈 값도 따로 저장한다.
  • 4방 탐색을 하면서 다음 위치가 범위에 해당한다면
    • 새 배열 해당 위치에 나눈 값을 더한다.
    • 총 먼지값에도 더한다.
    • 원래의 먼지값에서 그 값을 뺀다.
  • 탐색을 다 하고 마지막으로 새 배열 중심값(원래 위치)에 남은 먼지를 더한다.
  • 총 먼지값에도 더한다. (이 부분을 빼먹어서 실수했다.)
• 탐색이 모두 끝났으므로 새로 만든 배열로 교체한다. 이 때, 새 배열에 공기청정기 위치를 저장하지 않았는데, 위치를 이미 변수로 저장하고 있어서 따로 추가하지 않았다.
• 모두 확산시킨 후에 현재 남아있는 먼지가 얼마나 있는지 반환한다.

private static int spreadDust() {
   int count = 0;
   int[][] next = new int[R][C];

   for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
         if (house[r][c] < 1) continue;

         int dust = house[r][c];
         int divide = dust / 5;

         for (int d = 0; d < 4; d++) {
            int nr = r + deltas[d][0];
            int nc = c + deltas[d][1];
            if (valid(nr, nc)) {
               next[nr][nc] += divide;
               count += divide;
               dust -= divide;
            }
         }

         next[r][c] += dust;
         count += dust; 
      }
   }

   house = next; 
   return count;
}

 

바람 회전 메서드

• up 파라미터로 바람 회전을 어느 방향으로 해야하는지 체크한다.
• 어느 방향인지에 따라 wind 첫 위치, 회전 방향을 설정한다.
• 미리 처음위치의 값을 save에 저장시키고 그 자리는 0으로 바꾼다. 공기청정기에서는 깨끗한 바람만 불기 때문이다. 이 부분이 내가 실수한 부분이다.
• 4방탐색을 하면서 범위체크에 실패했다면 방향을 바꾼다.
• save값과 house[다음위치] 값을 서로 바꾼다.
• wind 첫 위치를 다음위치로 바꾼다. 이 부분도 내가 실수한 부분이다.

private static int blowWind(boolean up) {
   int[] wind = up ? new int[]{cleanU, 1} : new int[]{cleanD, 1};
   int[][] delta = up ? new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}} : deltas;
   int save = house[wind[0]][wind[1]];
   house[wind[0]][wind[1]] = 0;

   int d = 0;
   while (d < 4) {
      int nr = wind[0] + delta[d][0];
      int nc = wind[1] + delta[d][1];

      if (!valid(nr, nc)) {
         ++d;
         continue;
      }

      int tmp = house[nr][nc];
      house[nr][nc] = save;
      save = tmp;
      wind = new int[]{nr,nc}; 
   }

   return save;
}

---

3. 결과