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

1. 문제

 

17144번: 미세먼지 안녕!

 

2. 풀이

크게 어려울 것이 없는 단순 구현문제다. 아래 풀이한 코드를 보면 충분히 흐름을 이해할 수 있을 것으로 생각된다. 다만, 해당 문제에서 가장 중요한 조건이 하나 있는데, 미세먼지 확산에 대한 것이다.

 

바로 미세먼지는 모든 칸에서 동시에 확산된다는 점인데, 이는 다시 말해 단순 반복문을 통해서 확산된 미세먼지가 동일한 쿼리 내에서 상호 영향을 주면 안된다는 얘기가 된다. 즉, 각 기준점의 확산량을 누적할 수 있는 별도의 배열을 선언해야 한다는 의미이며, 이 지점만 유의해서 풀이한다면 나머지는 손쉽게 해결할 수 있다.

 

3. 소스코드

public class Main {
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};
    static int R, C, T;
    static int[][] map;

    static int run(int upper, int lower) {
        while (T-- > 0) {
            spread();
            circulate(upper, lower);
        }

        return checkTotalParticulates();
    }

    static void spread() {
        int[][] temp = new int[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] <= 0) continue;
                int spread = map[i][j] / 5;
                int cnt = 0;
                
                // 네 방향으로 미세먼지가 확산될 수 있는지 확인 후, 임시 배열에 추가
                for (int dir = 0; dir < 4; dir++) {
                    int ny = i + dy[dir];
                    int nx = j + dx[dir];
                    if (isOutOfRange(ny, nx) || map[ny][nx] == -1) continue;
                    cnt++;
                    temp[ny][nx] += spread;
                }
                
                // 원래 지점의 남은 미세먼지 양 처리
                temp[i][j] -= spread * cnt;
            }
        }
        
        // 임시 배열에 있던 확산된 미세먼지를 정산해줌
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] += temp[i][j];
            }
        }
    }

    static boolean isOutOfRange(int y, int x) {
        return y < 0 || x < 0 || R <= y || C <= x;
    }
    
    // 공기청정기의 윗부분과 아랫부분을 기준으로 순환 처리
    static void circulate(int upper, int lower) {
        // upper side
        int y = upper - 1;
        int x = 0;
        int dir = 0;
        while (true) {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            
            // rotate 처리를 위해, 노드가 지도 밖으로 나가는 경우 방향을 전환해줌
            if (isOutOfRange(ny, nx) || ny > upper) {
                // '북 > 동 > 남 > 서'
                dir = (dir + 1) % 4;
                ny = y + dy[dir];
                nx = x + dx[dir];
            }

            // 공기청정기를 만나는 경우 미세먼지가 사라지는 것 처리
            if (map[ny][nx] == -1) {
                map[y][x] = 0;
                break;
            }
            map[y][x] = map[ny][nx];
            y = ny;
            x = nx;
        }

        y = lower + 1;
        x = 0;
        dir = 2;
        while (true) {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (isOutOfRange(ny, nx) || ny < lower) {
                dir = (dir + 3) % 4;
                ny = y + dy[dir];
                nx = x + dx[dir];
            }

            if (map[ny][nx] == -1) {
                map[y][x] = 0;
                break;
            }
            map[y][x] = map[ny][nx];
            y = ny;
            x = nx;
        }
    }

    static int checkTotalParticulates() {
        int tot = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] != -1) {
                    tot += map[i][j];
                }
            }
        }
        return tot;
    }

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

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

        map = new int[R][C];

        int upper = 0; // 위쪽 공기청정기 position
        int lower = 0; // 아래쪽 공기청정기 position

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == -1) {
                    if (upper == 0) {
                        upper = i;
                    } else {
                        lower = i;
                    }
                }
            }
        }

        bw.write(run(upper, lower) + "");
        bw.close();
        br.close();
    }

}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code