algorithm/problem solving
BOJ 17144 미세먼지 안녕!
무니웜테일패드풋프롱스
2020. 6. 28. 14:30
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
문제 설명에 나온대로 구현하면 되는 시뮬레이션 문제이다.
- 확산: 4방향으로, 모든 미세먼지가 동시에 확산된다.
- 정화: 공기청정기의 윗부분과 아랫부분의 바람의 방향에 따라서 미세먼지의 자리가 옮겨진다.
로직은 아래와 같다.
- BFS로 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());
}
}