[BOJ] 17144 미세먼지안녕 - Java

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

17144번: 미세먼지 안녕!

[풀이]

1. 존재하는 미세먼지를 확산시킨다. 한 번에 확산시켜야 하므로 모든 칸을 돌면서 Plus와 Minus를 구하고, 다 돌면 한 번에 갱신한다.

2. 공기청정기 시계방향, 반시계 방향 회전시킨다.

회전시키는게 골때린다.

일단 공기청정기는 무시하고 일반적으로 시계방향으로 회전시키는 것을 생각해보자.

1) 순환하므로 값이 사라지는 것이 존재할 것이다.

그 점을 빨간색칸이라고 해보고, 그 값을 tmp에 저장해둔다. 그리고 회전을 다 돌린 후 빨간 칸이 진행할 방향의 칸에 빵꾸를 채워준다.

2) 회전을 시켜보자. 빨간칸에 들어오는 애부터 채워넣어보자. (보라색)

보라색의 start칸은 빨간칸에 들어온다. start칸 오른쪽 칸은 start에 들어온다. 이를 수도코드로 작성하면 그림의 보라색 글씨와 같다.

그리고 순서대로 초록색, 핑크색, 청록색을 수행하며 값들을 밀어나간다.

3) 청록색까지 하고 나면 적색 칸에는 아무 값도 들어와 있지 않다.  그러므로 아까 저장해두었던 빨간칸 값을 저장한다. Map[A-1][1] = tmp

 

비록 문제와는 반대 방향으로 그리긴했지만.. 그래도 같은 원리로 문제에 적용하면 된다.

문제에서는 공기청정기부분은 회전하지않으므로 생각해서 좌표를 지정하자. -> 코드로 확인! 

 

 

[코드]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj17144_미세먼지안녕 {
    static StringTokenizer st;
    static int R,C,T;
    static int[][] Map;
    static int[][] Plus;
    static int[][] Minus;
    static int answer;
    static int[] dRow = {-1,1,0,0};
    static int[] dCol = {0,0,-1,1};
    static int A,B;
    
    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        Map = new int[R+1][C+1];
       
        
        for(int i=1;i<R+1;i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=1;j<C+1;j++) {
        		Map[i][j] =  Integer.parseInt(st.nextToken());
        		if(Map[i][j]==-1) {
        			if(A==0) {
        				A = i;
        			}
        			else {
        				B = i;
        			}
        		} 
        	}
        }
        
        for(int t=0;t<T;t++) { //T초동안
        	 Plus = new int[R+1][C+1];
             Minus = new int[R+1][C+1];
        	//확산
             for(int i=1;i<R+1;i++) {
             	for(int j=1;j<C+1;j++) {
             		if(Map[i][j]!=-1 && Map[i][j]>0) { //공기청정기가 아니고, 미세먼지이면
             			int unit = Map[i][j] / 5;
             			for(int d=0;d<4;d++) { //4방으로 고고
                 			int newRow = i + dRow[d];
                 			int newCol = j + dCol[d];
                 			if(0<newRow && newRow<=R && 0<newCol && newCol<=C) { //범위 검사
                 				if(Map[newRow][newCol]!=-1) { //공기청정기가 아니면
                 					Plus[newRow][newCol] += unit;
                 					Minus[i][j] -= unit;
                 				}
                 			}
                 		}
             		}
             	}
             }
             //한번에 업데이트
             for(int i=1;i<R+1;i++) {
              	for(int j=1;j<C+1;j++) {
              		Map[i][j] += Plus[i][j];
              		Map[i][j] += Minus[i][j];
              	}
             }

            //printMap();
            for(int i=A-2;i>=1;i--){
                Map[i+1][1] = Map[i][1]; //아래로밀기
            }
            for(int j=2;j<=C;j++){ //왼쪽으로밀기
                Map[1][j-1] = Map[1][j];
            }
            for(int i=2;i<=A;i++){
                Map[i-1][C] = Map[i][C]; //위로밀기
            }
            for(int j=C-1;j>=2;j--){
                Map[A][j+1] = Map[A][j]; //오른쪽으로밀기
            }
            Map[A][2] = 0;
            //printMap();
            
            for(int i=B+2;i<=R;i++) { //위로밀기
            	Map[i-1][1] = Map[i][1];
            }
            for(int j=2;j<=C;j++) { //왼쪽으로밀기
            	Map[R][j-1] = Map[R][j];
            }
            for(int i=R-1;i>=B;i--) { //아래로밀기
            	Map[i+1][C] = Map[i][C];
            }
            for(int j=C-1;j>=2;j--) { //오른쪽으로밀기
            	Map[B][j+1] = Map[B][j];
            }
            Map[B][2] = 0;
           
            //printMap();
        }
        
        for(int i=1;i<R+1;i++) {
        	for(int j=1;j<C+1;j++) {
        		answer += Map[i][j]; //공기청정기는 -1인데 그대로 더해지므로 밑에서 +2해줌
        	}
        }
        System.out.println(answer+2);
    }
    static void printMap() {
    	System.out.println("===============");
    	for(int i=1;i<R+1;i++) {
         	for(int j=1;j<C+1;j++) {
         		System.out.print(Map[i][j]+" ");
         	}
         	System.out.println();
         }
    }
}

[느낀점]

소요시간 : 1h 10min

회전시키는게 머리가 뽀개질 뻔했다. 

근데 이거 좀 자주 나오는 유형인 것 같다. 다음에 나왔을 때는 헤매지 않고 해야지