BOJ 17144 미세먼지 안녕!

 

17144번: 미세먼지 안녕!

문제 설명에 나온대로 구현하면 되는 시뮬레이션 문제이다.

• 확산: 4방향으로, 모든 미세먼지가 동시에 확산된다.
• 정화: 공기청정기의 윗부분과 아랫부분의 바람의 방향에 따라서 미세먼지의 자리가 옮겨진다.

로직은 아래와 같다. 

1.  BFS로 4방향 확산을 시켜준다. 여기서 확산시킨 미세먼지의 값은 변경해주되, 확산 된 미세먼지의 값은 다른 배열에 같은 위치에 저장(플러스) 해둔다.
2. 모든 위치의 미세먼지의 확산이 끝났다면, 저장해둔 확산된 미세먼지를 각 위치에 더해준다.
3. 공기청정기의 위치와 방향에 따라서 미세먼지의 위치를 변경시켜준다.
4. 이를 T번 반복하면 된다.

가장 까다로웠던건 공기청정기 - 정화였다. 각 방향별로 미세먼지를 양옆 혹은 앞뒤로 옮겨주어야 하므로 x y 축을 잘 따져야한다. 

하지만 이도 그렇게 어려운 과정은 아니므로 크게 어려운 문제는 아니라고 생각한다. 

 

1. 미세먼지 확산 (BFS + spread ( 확산된 미세먼지 더해주기 ) ) 

private static int[][]dustMap;
	private static int[][]MapCopy;
	private static boolean[][]visited;
	static int[]dx = {-1,1,0,0};
	static int[]dy= {0,0,-1,1};
	private static Queue<pair>queue = new LinkedList<pair>();
	private static void bfs(int sx, int sy) { //확산
		// 네개의 방향으로 확산.
		// 확산 후, 확산시킨 곳의 미세먼지는 변경해준다.
		// 다른 곳의 미세먼지는 MapCopy의 해당 위치에 저장해둔다.
		visited[sx][sy]=true;
		queue.add(new pair(sx, sy)); 
		while(!queue.isEmpty()) {
			pair polled= queue.poll();
			int x = polled.x;
			int y = polled.y;
			int cnt = 0; 
			int dust = dustMap[x][y]/5;
			for(int i =0 ; i<4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0 || ny<0 || nx>=R || ny>=C) continue;
				if(dustMap[nx][ny]==-1) continue;
				cnt++; //확산 시킨 칸의 수
				if(!visited[x][y]&&dustMap[nx][ny]!=0) {
					queue.add(new pair(nx,ny));
					visited[nx][ny]=true;
				}
				MapCopy[nx][ny]+=dust; // 확산
			}
			dustMap[x][y]=dustMap[x][y]-(dust*cnt); // 확산 후 변화 
		}
	}

	private static void spread() { // MapCopy에 있는 내용 옮기는 메서드
		for(int i =0 ; i<R; i++) {
			for(int j=0; j<C; j++) {
				dustMap[i][j]+=MapCopy[i][j];
			}
		}
	}

 

2. 정화 

	private static void move() { //공기청정기 가동 
		// 첫번째 공기청정기 위치 X1 0
		// 두번째 공기청정기 위치 X2 0
=
		dustMap[X1-1][0]=0;
		for(int i = X1-2 ; i>=0; i--) {
			dustMap[i+1][0]=dustMap[i][0];
		} 
		dustMap[0][0]=dustMap[0][1]; 
		for(int i = 1; i<C ; i++) {
			dustMap[0][i-1]=dustMap[0][i];
		} 
		dustMap[0][C-1]= dustMap[1][C-1];
		for(int i = 2; i<=X1; i++) {
			dustMap[i-1][C-1]=dustMap[i][C-1];
		}
		dustMap[X1][C-1]=dustMap[X1][C-2];
		for(int i= C-2; i > 1 ; i--) {
			dustMap[X1][i]=dustMap[X1][i-1];
		}
		dustMap[X1][1]=0;
		
		//두번째 공기청정기
		dustMap[X2+1][0]=dustMap[X2+2][0];
		for(int i = X2+2 ; i+1<R; i++) {
			dustMap[i][0]=dustMap[i+1][0];
		}  
		dustMap[R-1][0]=dustMap[R-1][1]; 
		for(int i = 1; i<C ; i++) {
			dustMap[R-1][i-1]=dustMap[R-1][i];
		} 
	
		dustMap[R-1][C-1]=dustMap[R-2][C-1];
		for(int i = R-3; i>=X2; i--) {
			dustMap[i+1][C-1]=dustMap[i][C-1];
		}
		dustMap[X2][C-1]=dustMap[X2][C-2];
		for(int i= C-2; i > 1 ; i--) {
			dustMap[X2][i]=dustMap[X2][i-1];
		}
		dustMap[X2][1]=0;
	}
	

 

 

전체 코드는 아래와 같다.

import java.io.*;
import java.util.*;
class pair{
	int x;
	int y;
	pair(int x, int y){
		this.x=x;
		this.y=y;
	}
}
public class Main {
	private static int R;
	private static int C;
	private static int T;
	private static int X1=-1; //공기청정기 1 의 위치 저장 
	private static int X2; // 공기청정기 2의 위치 저장 
	private static int[][]dustMap;
	private static int[][]MapCopy;
	private static boolean[][]visited;
	static int[]dx = {-1,1,0,0};
	static int[]dy= {0,0,-1,1};
	private static Queue<pair>queue = new LinkedList<pair>();
	private static void bfs(int sx, int sy) { //확산
		// 네개의 방향으로 확산.
		// 확산 후, 확산시킨 곳의 미세먼지는 변경해준다.
		// 다른 곳의 미세먼지는 MapCopy의 해당 위치에 저장해둔다.
		visited[sx][sy]=true;
		queue.add(new pair(sx, sy)); 
		while(!queue.isEmpty()) {
			pair polled= queue.poll();
			int x = polled.x;
			int y = polled.y;
			int cnt = 0; 
			int dust = dustMap[x][y]/5;
			for(int i =0 ; i<4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0 || ny<0 || nx>=R || ny>=C) continue;
				if(dustMap[nx][ny]==-1) continue;
				cnt++; //확산 시킨 칸의 수
				if(!visited[x][y]&&dustMap[nx][ny]!=0) {
					queue.add(new pair(nx,ny));
					visited[nx][ny]=true;
				}
				MapCopy[nx][ny]+=dust; // 확산
			}
			dustMap[x][y]=dustMap[x][y]-(dust*cnt); // 확산 후 변화 
		}
	}
	
	private static void spread() { // MapCopy에 있는 내용 옮기는 메서드
		for(int i =0 ; i<R; i++) {
			for(int j=0; j<C; j++) {
				dustMap[i][j]+=MapCopy[i][j];
			}
		}
	}
	
	private static void move() { //공기청정기 가동 
		// 첫번째 공기청정기 위치 X1 0
		// 두번째 공기청정기 위치 X2 0
=
		dustMap[X1-1][0]=0;
		for(int i = X1-2 ; i>=0; i--) {
			dustMap[i+1][0]=dustMap[i][0];
		} 
		dustMap[0][0]=dustMap[0][1]; 
		for(int i = 1; i<C ; i++) {
			dustMap[0][i-1]=dustMap[0][i];
		} 
		dustMap[0][C-1]= dustMap[1][C-1];
		for(int i = 2; i<=X1; i++) {
			dustMap[i-1][C-1]=dustMap[i][C-1];
		}
		dustMap[X1][C-1]=dustMap[X1][C-2];
		for(int i= C-2; i > 1 ; i--) {
			dustMap[X1][i]=dustMap[X1][i-1];
		}
		dustMap[X1][1]=0;
		
		//두번째 공기청정기
		dustMap[X2+1][0]=dustMap[X2+2][0];
		for(int i = X2+2 ; i+1<R; i++) {
			dustMap[i][0]=dustMap[i+1][0];
		}  
		dustMap[R-1][0]=dustMap[R-1][1]; 
		for(int i = 1; i<C ; i++) {
			dustMap[R-1][i-1]=dustMap[R-1][i];
		} 
	
		dustMap[R-1][C-1]=dustMap[R-2][C-1];
		for(int i = R-3; i>=X2; i--) {
			dustMap[i+1][C-1]=dustMap[i][C-1];
		}
		dustMap[X2][C-1]=dustMap[X2][C-2];
		for(int i= C-2; i > 1 ; i--) {
			dustMap[X2][i]=dustMap[X2][i-1];
		}
		dustMap[X2][1]=0;
	}
	
	private static int getSum() { // 전체 미세먼지 수 반환 
		int sum = 0;
		for(int i =0 ; i< R; i ++) {
			for(int j=0; j<C; j++) {
				if(dustMap[i][j]==-1) continue;
				sum+=dustMap[i][j];
			}
		}
		return sum;
	}
	private static int solve() {
		for(int t =0 ; t<T; t++) {
			// 확산
			for(int i = 0 ; i <R; i++) {
				for(int j =0; j<C; j++) {
					if(dustMap[i][j]!=-1 && dustMap[i][j]!=0 && visited[i][j]!=true) {
						bfs(i,j);
					}
				}
			}
			spread(); 			
			move();
			
			//visited, copy 갱신
			for(int i=0; i< R; i++) {
				for(int j=0; j<C; j++) {
					MapCopy[i][j]=0;
					visited[i][j]=false;
				}
			}
		}
		return getSum();
	}
	
	public static void main(String[]args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());	
		T = Integer.parseInt(st.nextToken());
		
		dustMap = new int[R][C];
		MapCopy = new int[R][C];
		visited = new boolean[R][C];
		String []s;
		for(int i = 0 ; i < R; i++) {
			s = br.readLine().split(" ");
			for(int j =0 ; j < C; j ++) {
				dustMap[i][j]=Integer.parseInt(s[j]);
				if(dustMap[i][j]==-1) {
					if(X1==-1) { X1= i; } // 공기청정기 1 
					else { X2 = i;} //공기청정기 2 
				}
			}
		}
		System.out.println(solve());
	}
}