[백준 17144, Java] 미세먼지 안녕!

문제

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

문제이해

 

 "확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다." 를 잘못구현했다. 처음에는 for문으로 하나씩 돌면서 배열에 확산된 후의 양을 카운트 했다. 이거는 동시에 확산되는게 아니라 순차적으로 확산되는 거다. 따라서 확산량을 카운트 하기위한 배열을 따로 만든 후, 카운트가 끝나면 원래의 배열에 확산량을 더해줘야한다.(그리고 for 문으로 순차적으로 돌면 미세먼가 확산된 곳에 재확산이 발생한다)

 

 

 

구현

 

1. 첫번째 버전

 - 공기청정기가 작동하는 부분의 구현을 시계방향/ 반시계방향 2가지로 나눠서 구현했다. 너무 장황하다. 일단 간결하게 하는 건 나중으로 하고 제출. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line;
        StringTokenizer st;

        int R;
        int C;
        int T;
        int[][] home;
        ArrayList<Integer> airFresher = new ArrayList<Integer>();

        line = br.readLine();
        st = new StringTokenizer(line, " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        home = new int[R][C];
        for(int r = 0; r<R; r++){
            line = br.readLine();
            st = new StringTokenizer(line," ");

            for(int c=0; c<C; c++){
                int value = Integer.parseInt(st.nextToken());
                home[r][c] = value;

                if(value ==-1){
                    airFresher.add(r);
                }
            }
        }

        MicroDust microDust = new MicroDust(R,C,T,home,airFresher);

        for(int t=0;t<T;t++){
            microDust.spreadDust();
            microDust.operateAirFresherCounterClockWise(airFresher.get(0),0);
            microDust.operateAirFresherClockWise(airFresher.get(1),0);
        }
        bw.write(String.valueOf(microDust.countFineDust()));
        bw.flush();
    }
}
class MicroDust{
    int R;
    int C;
    int T;
    int[][] home;
    boolean[][] isDust;
    int[][] addedDust;
    ArrayList<Integer> airFresher;

    int[] dr = {0,1,0,-1};
    int[] dc = {1,0,-1,0};

    MicroDust(int R, int C, int T, int[][] home, ArrayList<Integer> airFresher){
        this.R = R;
        this.C = C;
        this.T = T;
        this.home = home;
        this.airFresher = airFresher;
        isDust = new boolean[R][C];
    }
    public void spreadDust(){
        findDust();
        addedDust = new int[R][C];

        for(int r=0;r<R; r++){
            for(int c=0;c<C; c++){
                if(isDust[r][c]){
                    addedDust[r][c]-=totalSpreadAmount(r,c);
                }
            }
        }

        for(int r=0;r<R;r++){
            for(int c=0;c<C; c++){
                home[r][c] += addedDust[r][c];
            }
        }
    }

    private void findDust(){
        for(int r= 0;r<R; r++){
            for(int c=0;c<C; c++){
                if(home[r][c]>0){
                    isDust[r][c]=true;
                }
            }
        }
    }
    private int totalSpreadAmount(int row, int column){
        int spreadAmount = home[row][column]/5;
        int spreadCount = 0;

        for(int index=0;index<4;index++){
                int x = row +dr[index];
                int y = column +dc[index];

                if(x>=0 && x <R && y>=0 && y <C){
                    if(home[x][y]>=0){
                        addedDust[x][y] += spreadAmount;
                        ++spreadCount;
                    }
                }
        }
        return spreadAmount*spreadCount;
    }

    public void operateAirFresherCounterClockWise(int r, int c){
        //시계 반대방향
        int x = r;
        int y = c;
        int tempbefore =0;
        int tempAfter = 0;

        //오른쪽 이동
        while(true){
            x= x + dr[0];
            y= y+ dc[0];

            if(y>=C){
                --y;
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }

        //위로 이동
        while(true){
            x= x + dr[3];
            y= y+ dc[3];

            if(x<0){
                ++x;
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }

        //왼쪽 이동
        while(true){
            x= x + dr[2];
            y= y+ dc[2];

            if(y<0){
                ++y;
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }

        //아래로 이동
        while(true){
            x= x + dr[1];
            y= y+ dc[1];

            if(home[x][y]==-1){
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }

    }

    public void operateAirFresherClockWise(int r, int c){
        //시계 방향
        int x = r;
        int y = c;
        int tempbefore =0;
        int tempAfter = 0;

        //오른쪽 이동
        while(true){
            x= x + dr[0];
            y= y+ dc[0];

            if(y>=C){
                --y;
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }

        //아래로 이동
        while(true){
            x= x + dr[1];
            y= y+ dc[1];

            if(x>=R){
                --x;
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }
        //왼쪽 이동
        while(true){
            x= x + dr[2];
            y= y+ dc[2];

            if(y<0){
                ++y;
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }
        //위로 이동
        while(true){
            x= x + dr[3];
            y= y+ dc[3];

            if(home[x][y]==-1){
                break;
            }
            else{
                tempAfter = home[x][y];
                home[x][y] = tempbefore;
                tempbefore = tempAfter;
            }
        }





    }
    public int countFineDust(){
        int total=0;
        for(int r= 0;r<R;r++){
            for(int c= 0;c<C;c++){
                total+=home[r][c];
            }
        }
        return total+2;
    }
    public void showHome(){
        for(int r= 0;r<R;r++){
            for(int c=0;c<C;c++){
                System.out.print(home[r][c]+" ");
            }
            System.out.println();
        }
    }

    public void showAddedDust(){
        for(int r= 0;r<R;r++){
            for(int c=0;c<C;c++){
                System.out.print(addedDust[r][c]+" ");
            }
            System.out.println();
        }
    }

}

 

2. 두번째 버전 

- 시계방향 회전/ 반시계 방향 회전을 하나의 메서드로 구현했다. 기존 메서드에 "뱡향"을 구분할 수 있도록 매개변수를 하나 더 추가를 했다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line;
        StringTokenizer st;

        int R;
        int C;
        int T;
        int[][] home;
        ArrayList<Integer> airFresher = new ArrayList<Integer>();
        int[] clockWise = {0,1,2,3};
        int[] counterClockWise = {0,3,2,1};

        line = br.readLine();
        st = new StringTokenizer(line, " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        home = new int[R][C];
        for(int r = 0; r<R; r++){
            line = br.readLine();
            st = new StringTokenizer(line," ");

            for(int c=0; c<C; c++){
                int value = Integer.parseInt(st.nextToken());
                home[r][c] = value;

                if(value ==-1){
                    airFresher.add(r);
                }
            }
        }

        MicroDust microDust = new MicroDust(R,C,T,home,airFresher);
        for(int t=0;t<T;t++){
            microDust.spreadDust();
            microDust.operateAirFresher(airFresher.get(0),0,counterClockWise);
            microDust.operateAirFresher(airFresher.get(1),0,clockWise);
        }
        bw.write(String.valueOf(microDust.countFineDust()));
        bw.flush();
    }
}
class MicroDust{
    int R;
    int C;
    int T;
    int[][] home;
    boolean[][] isDust;
    int[][] addedDust;
    ArrayList<Integer> airFresher;

    int[] dr = {0,1,0,-1};
    int[] dc = {1,0,-1,0};

    MicroDust(int R, int C, int T, int[][] home, ArrayList<Integer> airFresher){
        this.R = R;
        this.C = C;
        this.T = T;
        this.home = home;
        this.airFresher = airFresher;
        isDust = new boolean[R][C];
    }
    public void spreadDust(){
        findDust();
        addedDust = new int[R][C];

        for(int r=0;r<R; r++){
            for(int c=0;c<C; c++){
                if(isDust[r][c]){
                    addedDust[r][c]-=totalSpreadAmount(r,c);
                }
            }
        }

        for(int r=0;r<R;r++){
            for(int c=0;c<C; c++){
                home[r][c] += addedDust[r][c];
            }
        }
    }

    private void findDust(){
        for(int r= 0;r<R; r++){
            for(int c=0;c<C; c++){
                if(home[r][c]>0){
                    isDust[r][c]=true;
                }
            }
        }
    }
    private int totalSpreadAmount(int row, int column){
        int spreadAmount = home[row][column]/5;
        int spreadCount = 0;

        for(int index=0;index<4;index++){
                int x = row +dr[index];
                int y = column +dc[index];

                if(x>=0 && x <R && y>=0 && y <C){
                    if(home[x][y]>=0){
                        addedDust[x][y] += spreadAmount;
                        ++spreadCount;
                    }
                }
        }
        return spreadAmount*spreadCount;
    }

    public void operateAirFresher(int r, int c, int[] directions){
        int x = r;
        int y = c;
        int tempbefore =0;
        int tempAfter = 0;

        for(int index = 0; index < directions.length; index++) {
            int direction = directions[index];

            while (true) {
                int tempX = x + dr[direction];
                int tempY = y + dc[direction];

                if (tempX<0||tempX>=R||tempY<0||tempY >= C || home[tempX][tempY]==-1) {
                    break;
                } else {
                    x = tempX;
                    y = tempY;
                    tempAfter = home[x][y];
                    home[x][y] = tempbefore;
                    tempbefore = tempAfter;
                }
            }
        }
    }

    public int countFineDust(){
        int total=0;
        for(int r= 0;r<R;r++){
            for(int c= 0;c<C;c++){
                total+=home[r][c];
            }
        }
        return total+2;
    }
    public void showHome(){
        for(int r= 0;r<R;r++){
            for(int c=0;c<C;c++){
                System.out.print(home[r][c]+" ");
            }
            System.out.println();
        }
    }

    public void showAddedDust(){
        for(int r= 0;r<R;r++){
            for(int c=0;c<C;c++){
                System.out.print(addedDust[r][c]+" ");
            }
            System.out.println();
        }
    }

}