[BaekJoon] 1736 쓰레기 치우기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int row;
    static int col;
    static int dustCount;
    static int[][] map;
    static PriorityQueue<Integer>[] dustLocs;

    static void input() {
        Reader scanner = new Reader();

        row = scanner.nextInt();
        col = scanner.nextInt();
        map = new int[row][col];
        dustLocs = new PriorityQueue[col];
        for (int c = 0; c < col; c++) {
            dustLocs[c] = new PriorityQueue<>();
        }

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                map[r][c] = scanner.nextInt();
                if (map[r][c] == 1) {
                    dustLocs[c].offer(r);
                    dustCount++;
                }
            }
        }
    }

    /*
     * 최소 개수의 로봇을 이용하여 청소하는 경우는 여러 방법이 있을 수 있겠지만
     * 가장 오른쪽부터 쓰레기를 청소하는 방법이 최소 개수의 로봇으로 청소하는 경우가 된다
     * 이때 가장 오른쪽에 있는 쓰레기들을 모두 청소하고 쓰레기들 중 가장 위에 위치한 쓰레기 높이를 이용하여
     * 왼쪽에 있는 쓰레기들 중 그보다 더 위에 있는 쓰레기들을 같이 치워준다
     * 예를 들어 아래와 같이 쓰레기가 있다고 하자
     *      0 1 0 0 0 0
     *      0 0 0 1 1 1
     *      0 1 1 0 0 1
     *      0 0 0 0 0 0
     *      1 0 0 1 0 0
     *  - 여기서 가장 오른쪽에 위치한 쓰레기들을 먼저 치운다
     *  - 그러면 최저 높이는 1이 된다
     *  - 로봇은 오른쪽, 아래쪽으로만 이동할 수 있기 때문에 이전에 구한 최저 높이보다 작거나 같은 높이에서 왼쪽에 있는 쓰레기들을 치울 수 있다
     *  - 그러므로 (1, 4) 쓰레기를 같이 치운다
     *  - 이후에는 column이 3인 곳에 있는 쓰레기들을 같이 치우는데, 최저 높이인 1보다 작거나 같은 쓰레기는 (1, 3) 뿐이므로 이 쓰레기를 같이 치운다
     *  - column이 2인 곳에 있는 쓰레기들은 모두 최저 높이 이후에 있는 쓰레기들이므로 같이 치울 수 없다
     *  - column이 1인 곳에 있는 쓰레기들 중에 최저 높이보다 작거나 같은 곳에 있는 쓰레기들은 (0, 1)이 있으니 이 쓰레기를 같이 치운다
     *      - 이때 최저 높이는 0으로 변경된다
     *  - column이 0인 곳에서 최저 높이 이하로 있는 쓰레기는 없으니 이렇게 같이 치운 쓰레기들이 하나의 로봇을 통해 청소된 쓰레기가 된다
     * 이러한 방식으로 쓰레기들을 청소해나가며 총 몇 대의 로봇이 필요한지 확인한다
     */
    static void solution() {
        int answer = 0;
        for (int count = 0; count < col; count++) {
            int dust = 0;
            int height = row - 1;
            for (int c = col - 1; c >= 0; c--) {
                if (dustLocs[c].size() == 0) {
                    continue;
                }
                int dustLoc = dustLocs[c].peek();
                if (height >= dustLoc) {
                    while (dustLocs[c].size() > 0 && height >= dustLocs[c].peek()) {
                        dustLocs[c].poll();
                        dust++;
                    }
                    height = dustLoc;
                }
            }

            if (dust > 0) {
                answer++;
            }
            if (dust == 0) {
                break;
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}