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

 

문제가 너무 길어 중략하겠다...

 

문제는 장황한데 로직 자체는 별거 없다.

삼성 SW 문제들은 기본 탐색 + 문제 해결/구현 조합으로 자주 나오는데

문제에 접근하는것 자체는 어렵지 않아 흥미가 붙는 느낌이다.

 

문제 진행은 다음과 같다.

1. BFS 로 1회 탐색하며 문제에서 요구하는 대로 미세먼지를 퍼트린다.

2. 공기청정기를 문제에서 요구하는 대로 작동시켜 미세먼지를 뒤로 민다.

3. 입력받은 시간만큼 반복한 후 미세먼지의 양을 출력한다.

 

 

미세먼지 확산은 확산 과정에서 합연산으로 먼지가 쌓이므로

먼저 BFS를 1회 마친 후 큐에 담겨있는 노드들을 빼내면서 배열을 다시 채워준다.

그리고 다음 BFS에 미세먼지의 위치들을 큐에 담아 진행한다.

이때 공기청정기의 위치도 잊지말고 채워준다.

 

공기청정기 순환은 특별한 알고리즘없이 시계방향, 반시계방향으로 인덱스를 밀어주었다.

어떻게하면 깔끔하게 구현할 수 있을까 시간낭비하다가 주먹구구식으로 그냥 짰다ㅜㅜ

 

 

public class Main {
    
    static int r;
    static int c;
    static int t;
    static int a[][];
    static Pair cle1 = null;
    static Pair cle2 = null;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    
    public static void main(String[] args) throws Exception {
        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());
        a = new int[r][c];
        
        for(int i=0; i<r; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<c; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
                if(a[i][j] == -1 && cle1 == null)
                    cle1 = new Pair(i, j, -1);
                else if(a[i][j] == -1 && cle1 != null)
                    cle2 = new Pair(i, j, -1);
            }
        }
        
        while(t-->0) {
            bfs();
        }
        
        int sum = 0;
        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++)
                if(a[i][j] != -1)
                    sum += a[i][j];
        
        System.out.println(sum);
    }
    
    public static void bfs() {
        Queue<Pair> q = new LinkedList<Pair>();
        
        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++)
                if(a[i][j] != 0 && a[i][j] != -1)
                    q.offer(new Pair(i, j, a[i][j]));
        
        int size = q.size();
        
        while(size-->0) {
            Pair p = q.poll();
            int cnt = 0;
            for(int i=0; i<4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(0 <= nx && nx < r && 0 <= ny && ny < c) {
                    if(a[nx][ny] != -1) {
                        q.offer(new Pair(nx, ny, p.dust/5));
                        cnt++;
                    }
                }
            }
            q.offer(new Pair(p.x, p.y, p.dust - p.dust/5*cnt));
        }
        
        a = new int[r][c];
        a[cle1.x][cle1.y] = -1;
        a[cle2.x][cle2.y] = -1;
        
        while(!q.isEmpty()) {
            Pair p = q.poll();
            a[p.x][p.y] += p.dust;
        }
        
        nonclockWise(cle1.x, cle1.y);
        clockWise(cle2.x, cle2.y);
    }
    
    public static void nonclockWise(int x, int y) {
        int temp = 0;
        int last = 0;
        while(true) {
            if(y+1 >= c) break;
            temp = a[x][y+1];
            a[x][y+1] = last;
            last = temp;
            y++;
        }
        
        while(true) {
            if(x-1 < 0) break;
            temp = a[x-1][y];
            a[x-1][y] = last;
            last = temp;
            x--;
        }
        
        while(true) {
            if(y-1 < 0) break;
            temp = a[x][y-1];
            a[x][y-1] = last;
            last = temp;
            y--;
        }
        
        while(true) {
            if(x+1 >= r) break;
            temp = a[x+1][y];
            if(temp == -1) break;
            a[x+1][y] = last;
            last = temp;
            x++;
        }
    }
    
    public static void clockWise(int x, int y) {
        int temp = 0;
        int last = 0;
        while(true) {
            if(y+1 >= c) break;
            temp = a[x][y+1];
            a[x][y+1] = last;
            last = temp;
            y++;
        }
        
        while(true) {
            if(x+1 >= r) break;
            temp = a[x+1][y];
            a[x+1][y] = last;
            last = temp;
            x++;
        }
        
        while(true) {
            if(y-1 < 0) break;
            temp = a[x][y-1];
            a[x][y-1] = last;
            last = temp;
            y--;
        }
        
        while(true) {
            if(x-1 < 0) break;
            temp = a[x-1][y];
            if(temp == -1) break;
            a[x-1][y] = last;
            last = temp;
            x--;
        }
    }
    
    static class Pair {
        int x;
        int y;
        int dust;
        
        Pair(int x, int y, int dust) {
            this.x = x;
            this.y = y;
            this.dust = dust;
        }
    }
}