문제

BOJ 17144: 미세먼지 안녕! https://www.acmicpc.net/problem/17144

풀이

조건

• 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다.
• 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
• 1초 동안 아래 적힌 일이 순서대로 일어난다.
  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
     • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
     • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
     • 확산되는 양은 (Ar,c)/5이고 소수점은 버린다.
     • (r, c)에 남은 미세먼지의 양은 (Ar,c) - ((Ar,c)/5)×(확산된 방향의 개수) 이다.
       • 남은 미세먼지의 양에 옆에서 퍼져 온 미세먼지 양도 더해야한다.
  2. 공기청정기가 작동한다.
     • 공기청정기에서는 바람이 나온다.
     • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
     • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
     • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

풀이 순서

• 아래의 순서대로 주석을 보면 쉽다.
• 먼지 퍼트리기
  • Queue에 부모 먼지(원래 미세 먼지)의 좌표와 양을 넣는다.
  • Queue에서 차례로 꺼내고 4방향을 탐색한다.
  • 범위를 체크하고 새끼 먼지(퍼져나가는 미세 먼지)를 퍼트린다.
  • 이 때 새로운 배열(exMap)을 사용하여 갱신한다.
• 바람 순환하기
  • 조건에 맞게 윗 쪽 순환과 아랫 쪽 순환을 따로 구현한다.
  • 백준의 배열 돌리기 문제 처럼 회전 시킨다.
  • 이 때 윗 쪽 순환과 아랫 쪽 순환의 범위를 잘 해줘야 한다.

코드

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

public class Main {  
	
   static int R, C, T;
   static int[][] map;
   
   static int[] dx = {-1, 0, 1, 0};
   static int[] dy = {0, 1, 0, -1};
   
   static int[][] exMap;
  
   public static void main(String[] args) 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];
      Cir[] cir = new Cir[2]; // [0]: 위 쪽 공기청정기, [1]: 아래 쪽 공기청정기
      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(map[i][j] == -1) {
    			  cir[idx] = new Cir(i, j);
    			  idx++;
    		  }
    	  }
      }
      
      for(int i=1; i<=T; i++) {
    	  spreadDust(); // 먼지 퍼트리기
    	  circulating(cir[0], cir[1]); // 공기 순환
      }
      
      int ans = 0;
      for(int i=0; i<R; i++) {
    	  for(int j=0; j<C; j++) {
    		  ans += map[i][j];
    	  }
      }
      
      // 공기청정기 위치의 값은 -1 이므로 +2 해줌
      System.out.println(ans + 2);
   }   
   
   static void circulating(Cir up, Cir below) {
	   // 위 쪽 순환
	   int idx = 0;
	   int x = up.x;
	   int y = up.y;
	   while(true) {
		   int nx = x + dx[idx];
		   int ny = y + dy[idx];
		   
		   // 범위 벗어나면 idx 바꿔줌
		   if(nx < 0 || ny < 0 || nx > up.x || ny >= C) {
			   idx = (idx + 1) % 4;
			   continue;
		   }
		   
		   if(map[x][y] == -1) { // 순환 시작인 상황
			   
		   } else if(map[nx][ny] == -1) { // 순환 마지막 상황 -> 공기청정기에서 나가는 공기는 먼지 농도 0
			   map[x][y] = 0;
			   break;
		   } else { // 공기 순환
			   map[x][y] = map[nx][ny];
		   }
		   
		   x = nx;
		   y = ny;	   
	   }
	   
	   // 아래쪽 순환
	   idx = 3;
	   x = below.x;
	   y = below.y;
	   while(true) {
		   int nx = x + dx[idx];
		   int ny = y + dy[idx];
		   
		   // 범위 벗어나면 idx 바꿔줌
		   if(nx < below.x || ny < 0 || nx >= R || ny >= C) {
			   idx = idx - 1;
			   if(idx < 0) {
				   idx = 3;
			   }
			   continue;
		   }
		   
		   if(map[x][y] == -1) { // 순환 시작인 상황
			   
		   } else if(map[nx][ny] == -1) { // 순환 마지막 상황 -> 공기청정기에서 나가는 공기는 먼지 농도 0
			   map[x][y] = 0;
			   break;
		   } else { // 공기 순환
			   map[x][y] = map[nx][ny];
		   }
		   
		   x = nx;
		   y = ny;	   
	   }
	   
   }
   
   static void spreadDust() {
	   exMap = new int[R][C]; // 4방향으로 퍼진 새끼 먼지 농도 표시할 배열
	   
	   // 초기 상태인 부모 먼지 상태를 Queue에 넣음
	   Queue<Dust> que = new LinkedList<>(); 
	   for(int i=0; i<R; i++) {
		   for(int j=0; j<C; j++) {
			   if(map[i][j] != 0 && map[i][j] != -1) {
				   que.add(new Dust(i, j, map[i][j]));
			   }
		   }
	   }
	   
	   while(!que.isEmpty()) {
		   Dust dust = que.poll(); // 부모 먼지 객체
		   
		   int curX = dust.x;
		   int curY = dust.y;
		   int curVol = dust.vol;
		   
		   int cnt = 0;
		   int nVol = curVol / 5; // 새끼 먼지의 농도
		   for(int t=0; t<4; t++) {
			   int nx = curX + dx[t];
			   int ny = curY + dy[t];
			   
			   // 범위를 벗어났거나 공기청정기가 있는 위치는 먼지 퍼트리기 불가능
			   if(nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == -1) continue;
			   
			   cnt++; // 먼지가 퍼질 수 있는 방향의 갯수
			   // 배열에 새끼 먼지 농도를 중첩해줌
			   exMap[nx][ny] += nVol;
			     
		   }
		   // 부모 먼지의 농도 갱신
		   int nRootVol = curVol - (nVol * cnt);
		   map[curX][curY] = nRootVol;
		   
	   }
	   
	   // 갱신된 부모 먼지의 농도가 표시된 map배열에 새끼 먼지 농도를 더해줌
	   for(int i=0; i<R; i++) {
		   for(int j=0; j<C; j++) {
			   map[i][j] += exMap[i][j];
		   }
	   }
   
   }
   
   // 먼지의 위치, 농도
   static class Dust{
	   int x, y, vol;
	   
	   Dust(int x, int y, int vol){
		   this.x = x;
		   this.y = y;
		   this.vol = vol;
	   }
   }
   
   // 공기 청정기의 위치
   static class Cir{
	   int x, y;
	   
	   Cir(int x, int y){
		   this.x = x;
		   this.y = y;
	   }
   }
   
}

정리

• 순환 시킬 때 범위를 잘못 지정해서 순환이 제대로 되지 않아 시간 낭비를 했다.