백준 17144 미세먼지 안녕!

상반기 삼성 코딩테스트 기출문제이다.

상반기에 단기간에 공부해서 시험치러 갔다가 결국 런타임 에러를 잡지 못하고 와서 멘탈이 나갔었다..

평생 잊을 수 없는 문제가 될 것 같다.

그 후로 풀고 싶었지만 문제를 보고 싶지 않아서 다른 문제들을 먼저 다 풀었다.

결국 백준에 있는 다른 기출 문제들을 다 푼후에 다시 풀게 되었다.

 

당시에는 runtime에러를 어떻게 찾아야 할 지 감도 잡지 못했었다. 배열을 참조할 때 인덱스가 벗어났을 것이라 생각해서 1시간이 넘는 시간 동안 이를 찾다가 결국 시간 안에 풀지 못하고 나왔던 아픈 경험이었다.

 

그리고 다시 c++이 아닌 Java로 풀게 되었다. 문제를 한 번 봤던 탓인지 문제가 어렵지 않았다.

 

문제를 많이 풀어보면서 굳이 배열이 주어져도 배열에서 움직이는 것이 아니라 arraylist에 좌표값을 넣어서 이를 가지고 해결하는 방법을 알게 되었고, 이 문제도 역시 미세 먼지가 있는 곳의 위치를 arraylist에 보관하여 풀었다.

 

단지 포인트라면 먼지를 확산시키기 위해서는 기존의 미세 먼지 양을 저장하고 있는 2차원 배열과 확산시키면서 그 값을 저장하는 2차원 배열을 따로 둔 것이었다. 당시에 이를 생각하지 못해서 당황했던 기억이 있다.

그리고 또 하나의 포인트는 공기 청정기를 통해 미세먼지를 이동시키는 것이다. 당시에 여기서 런타임 에러가 났다고 생각해서 계속 확인했지만 결국 찾지 못했었다. 그리고 코드도 조금 복잡하게 짰던 것으로 기억한다.

 

하지만 지금 다시보니 간단하게 for문 몇 줄로 처리할 수 있었다. 

아래는 코드이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main17144 {
    static int ans;
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
 
        int cleaner1 = 0, cleaner2 = 0;
        int[][] map = new int[r][c];
        ArrayList<int[]> mess = new ArrayList<>();
        boolean flag = true;
        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 && map[i][j] != 0) {
                    int[] temp = { i, j };
                    mess.add(temp);
                }
                if (map[i][j] == -1 && flag) {
                    cleaner1 = i;
                    cleaner2 = i + 1;
                    flag = false;
                }
            }
        }
 
        while (t-- > 0) {
            int[][] after = new int[r][c];
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    after[i][j] = map[i][j];
                }
            }
//            System.out.println("확산 전");
//            for (int i = 0; i < r; i++) {
//                for (int j = 0; j < c; j++) {
//                    System.out.format("%3d", map[i][j]);
//                }
//                System.out.println();
//            }
//            System.out.println();
//            System.out.println("미세먼지 위치");
//            System.out.println("사이즈 " + mess.size());
//            for(int[] ar : mess)
//                System.out.println(ar[0] + " " + ar[1]);
            for (int i = 0; i < mess.size(); i++) {
                int row = mess.get(i)[0];
                int col = mess.get(i)[1];
 
                for (int j = 0; j < 4; j++) {
                    int nr = row + dr[j];
                    int nc = col + dc[j];
 
                    if (nr < 0 || nr >= r || nc < 0 || nc >= c)
                        continue;
                    if (map[nr][nc] == -1)
                        continue;
                    after[row][col] -= (map[row][col] / 5);
                    after[nr][nc] += (map[row][col] / 5);
                }
            }
//            System.out.println("확산 후");
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    map[i][j] = after[i][j];
//                    System.out.format("%3d", map[i][j]);
                }
//                System.out.println();
            }
//            System.out.println();
 
            // 청정기 위 왼쪽
            for (int i = cleaner1 - 1; i > 0; i--)
                map[i][0] = map[i - 1][0];
            // 청정기 아래 왼쪽
            for (int i = cleaner2 + 1; i < r - 1; i++)
                map[i][0] = map[i + 1][0];
            // 제일 위줄
            for (int i = 0; i < c - 1; i++)
                map[0][i] = map[0][i + 1];
            // 제일 아래 줄
            for (int i = 0; i < c - 1; i++)
                map[r - 1][i] = map[r - 1][i + 1];
            // 청정기 위 오른쪽
            for (int i = 0; i < cleaner1; i++)
                map[i][c - 1] = map[i + 1][c - 1];
            // 청정기 아래 오른쪽
            for (int i = r - 1; i > cleaner2; i--)
                map[i][c - 1] = map[i - 1][c - 1];
            // 가운데 두 줄
            for (int i = c - 1; i > 1; i--) {
                map[cleaner1][i] = map[cleaner1][i - 1];
                map[cleaner2][i] = map[cleaner2][i - 1];
            }
            map[cleaner1][1] = 0;
            map[cleaner2][1] = 0;
 
//            System.out.println("이동 후");
//            for (int i = 0; i < r; i++) {
//                for (int j = 0; j < c; j++) {
//                    System.out.format("%3d", map[i][j]);
//                }
//                System.out.println();
//            }
//            System.out.println();
            
            mess.clear();
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (map[i][j] != 0 && map[i][j] != -1) {
                        int[] temp = { i, j };
                        mess.add(temp);
                    }
                }
            }
//            System.out.println("미세먼지 위치");
//            System.out.println("사이즈 " + mess.size());
//            for(int[] ar : mess)
//                System.out.println(ar[0] + " " + ar[1]);
        }
        int ans = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] != -1)
                    ans += map[i][j];
            }
        }
        System.out.println(ans);
    }
 
}