BOJ_17144_미세먼지 안녕!

1

구분: 구현

언어: Java

전략

1. 먼지의 좌표와 먼지 양을 담을 클래스를 생성

2. 먼지를 큐에 담고, 4방을 탐색하며, 먼지를 확산시킨다. 단!! 먼지가 동시에 확산된다는 점을 잊지 말아야 한다

3. 공기 청정기 작동 - 하나하나 그림을 바탕으로 칸을 이동한다.

---

2. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	
	//먼지의 좌표와  먼지를 담을 class
	static class Point{
		int y, x, dust;
		Point(int y, int x, int dust){
			this.y = y;
			this.x = x;
			this.dust = dust;
		}
	}

	static int[][] map;
	static int h, w, up, down;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	static Queue<Point> q;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		h = scanner.nextInt();
		w = scanner.nextInt();
		int t = scanner.nextInt();
		int downy = -1;//공청기의 아래쪽 y좌표
		q = new LinkedList<>();
		map = new int[h][w];
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				map[i][j] = scanner.nextInt();
				if(map[i][j] == -1) {
					downy = i;
				}
			}
		}
		down = downy;//공청기의 아랫부분 y좌표
		up = downy - 1;//공청기의 윗부분 y좌표
		
		for(int i = 0; i<t; i++) {
			put();
			spread();
			cleaner();
		}
		
		System.out.println(getTotal());
				
		
	}//main
	
	//q에 미세먼지들을 넣는 함수 
	private static void put() {
		q = new LinkedList<>();
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				//공청기가 아니고, 빈칸이 아니라면 == 미세먼지라면
				if(map[i][j]!=0 && map[i][j]!=-1) 
					q.add(new Point(i, j, map[i][j]));
			}
		}
	}
	
	//미세먼지가 분산되는 모습
	private static void spread() {
		

			
			while(!q.isEmpty()) {
				Point p = q.poll();
				int px = p.x;
				int py = p.y;
				int pdust = p.dust;
			
				//확산되지 않음
				if(pdust<5)
					continue;
				
				int spreadCnt = 0;//총 몇개나 분산되었는가를 확인
				int sp = pdust / 5;
				
				for(int d = 0; d<4; d++) {
					int nx = px + dx[d];
					int ny = py + dy[d];
					
					if(!isOk(ny, nx))
						continue;
				
					//5로 나눈 것들을 분산
					map[ny][nx] += sp;

					spreadCnt++;
				}
				
				map[py][px] -= sp * spreadCnt;
		}
		
	}//spread
	
	//공청기 작동하는 함수 
	private static void cleaner() {
		//공청기 윗부분 - 반시계방향
		//맨 위에서 공청기까지 내려오기
		for(int i = up-1; i>0; i--) {
			map[i][0] = map[i-1][0];
		}
		//맨 윗줄, 가장 오른쪽에서 왼쪽으로
		for(int j = 0; j<=w-2; j++) {
			map[0][j] = map[0][j+1];
		}
		//가장 오른쪽, 아래에서 위로 
		for(int i = 0; i<=up-1; i++) {
			map[i][w-1] = map[i+1][w-1];
		}
		//공청기 줄, 오른쪽값을 왼쪽으로 넣어주기
		for(int j = w-1; j>=2; j--) {
			map[up][j] = map[up][j-1];
		}
		
		//공청기 아랫부분 - 시계방향
		for(int i = down+1; i<=h-2; i++) {
			map[i][0] = map[i+1][0];
		}
		for(int j = 0; j<=w-2; j++) {
			map[h-1][j] = map[h-1][j+1];
		}
		for(int i = h-1; i>=down+1; i--) {
			map[i][w-1] = map[i-1][w-1];
		}
		for(int j = w-1; j>=2; j--) {
			map[down][j] = map[down][j-1];
		}
		map[up][1] = map[down][1] = 0;
		//map[up][0] = map[down][0] = -1;
		
	}
	
	//좌표가 범위를 벗어나는가? 공청기 자리인가를 확인하는 함수 
	private static boolean isOk(int y, int x) {
		if(x<0 || y<0|| x>=w|| y>=h)
			return false;
		if(map[y][x] == -1)
			return false;
		return true;
	} 
	
	//전체 미세먼지를 구하는 함수  
	private static int getTotal() {
		int total = 2;
		
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				total+=map[i][j];
			}
		}
		return total;
	}
	

	

}

 

---

3

정말 오래 걸린 문제이다 

• 문제 1. 공기 청정기가 작동하여서 먼지가 퍼질때 - 가장 집중력이 필요하고, 복잡한 단계였다. 실수도 많고
• 문제 2. 먼지의 확산 - 먼지의 확산이 동시에 발생하기 때문에, sp라는 변수를 만들지 않고, map[py][px]를 그대로 사용하였다(계속 변하는데,,,). 또한 sp변수를 만들어도, 계속 변화하기 때문에 맨 처음 상태를 저장하기 위해 q에 넣을떄부터 저장을 해야 한다.
• 문제 3. 나 자신을 너무 믿음 - 아무리 생각해도 로직이 맞아서, 내가 실수하고 있다는 생각을 못한다. 계속 더 면밀하게 보지 못한다.