[백준 - 1736번] 쓰레기 치우기 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디

입력

첫 행에는 N, M이 공백으로 구분되어 주어진다.

다음 N 행에 걸쳐 M 개의 수가 주어진다. 이 값이 0이면 해당하는 위치가 비어 있다는 뜻이고, 1이면 해당하는 위치에 쓰레기가 있음을 뜻한다.

출력

필요한 최소 로봇의 수를 출력한다.

풀이

모든 쓰레기를 수거하기 위해서 최소 로봇의 수를 구하려면 아래 있는 쓰레기를 우선으로, 없다면 오른쪽 있는 쓰레기를 우선으로 수거하면 된다.

왜냐하면 로봇은 오른쪽, 아래로만 움직일 수 있다. 이 말은 로봇이 오른쪽으로 가면, 왼쪽에 있는 쓰레기는 수거할 수 없고, 아래로 움직이면 그 위에 있는 쓰레기는 수거할 수 없음을 의미한다.

그래서 만약 아래를 우선적으로 움직인다면, 아래에 쓰레기가 있는데도 오른쪽을 우선적으로 움직이는 경우가 없어야 한다.

그러니까 아래를 우선적으로 움직이면, 그 아래에 모든 쓰레기를 수거하고 나서야 다음 오른쪽으로 움직이는 것이 최적해인 것이다.

예를 들어 입력이 다음과 같을 때
3 3
1 0 1
1 1 1
0 1 1

첫 번째 로봇은 (0,0) -> (0,1) -> (1,1)로 움직이고, 여기서 (1,2)가 있는데 (2,1)로 움직인다면, (1,2)를 수거하기 위해 로봇 하나가 더 필요하게 된다. 그래서 (1,1) -> (1,2) -> (2,2)를 수거하고

두 번재 로봇이 (2,0)을 수거해서 최적해가 2가 된다.

그리디 풀이는 시간 복잡도 O(N*M)이다.

소스 코드

import java.io.*;
import java.util.*;

class Trash implements Comparable<Trash> {
    int x, y;
    boolean processed = false;
    Trash(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    @Override
    public int compareTo(Trash o) {
        if(this.x < o.x) {
            return -1;
        } else if(this.x > o.x) {
            return 1;
        } else {
            if(this.y < o.y) {
                return -1;
            } else if(this.y > o.y) {
                return 1;
            }
        }
        return 0;
    }
}

public class Main {
    static int N,M;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      ArrayList<Trash>[] col = new ArrayList[M];
      ArrayList<Trash> trashList = new ArrayList<>();
      for(int i=0; i<M; i++) {
          col[i] = new ArrayList<>();
      }
      
      for(int i=0; i<N; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          for(int j=0; j<M; j++) {
              if(Integer.parseInt(st2.nextToken()) == 1) {
                  Trash trash = new Trash(j, i);
                  col[j].add(trash);
                  trashList.add(trash);
              }
          }
      }
      Collections.sort(trashList);
      
      int answer = 0;
      for(int i=0; i<trashList.size(); i++) {
          if(!trashList.get(i).processed) {
              answer += 1;
              clean(trashList.get(i), col);
          }
      }
      System.out.println(answer);
  }
  
  static void clean(Trash start, ArrayList<Trash>[] col) {
      Trash cur = start;
      while(cur.x < M) {
          cur = clean(cur, col[cur.x]);
      }
  }
  
  static Trash clean(Trash cur, ArrayList<Trash> col) {
      Trash result = cur;
      if(col.size() != 0 && col.get(col.size() - 1).y >= cur.y) {
          result = col.get(col.size() - 1);
      }
      while(col.size() != 0 && col.get(col.size() - 1).y >= cur.y) {
          col.get(col.size() - 1).processed = true;
          col.remove(col.size() - 1);
      }
      result.x += 1;
      return result;
  }
  
}