백준 7576. 토마토

문제 링크

난이도	정답률(_%)
Silver 1	31.736%

설계

• 토마토 상자의 크기 가로 M, 세로 N (2 ~ 1000)
• 날짜를 증가시키면서 토마토를 익히는 방식은 일일히 익은 토마토를 찾아가야하기 때문에 시간이 너무 오래걸려서 불가능하다.
• 익은 토마토의 위치를 저장해두고, 그 위치의 주변을 익혀나가는 식으로 반복 (BFS)

시간 복잡도

• 익은 토마토의 개수에 따라 다르다..
• ?

공간 복잡도

• 토마토를 저장한 int형 배열 [n][m]
• 익은 토마토의 위치를 저장하는 Queue

풀이

• 토마토를 넣을 때 익은 토마토의 위치를 큐에, 안익은 토마토의 개수를 저장
• 토마토가 다 익은데 걸리는 시간 계산
  • 처음부터 안익은 토마토가 없으면 0일이 걸리는 것이기 때문에 바로 리턴
    • 굳이 리턴하지 않아도 되는 구문이지만 전부 익어있다는 것을 확인하는 과정이 오래걸릴 수 있기 때문에 리턴
  • 큐에 저장된 익은 토마토의 위치 주변을 익히고 새로 익은 토마토를 새로운 큐에 저장, 안익은 토마토의 수를 감소시킴
  • 기존에 있던 토마토들이 다 익으면 날짜를 증가시키고 새로 익은 토마토의 위치를 익은 토마토 큐로 옮김
    • 이 때 새로 익은 토마토가 없다면 익힐 수 있는 모든 토마토를 다 익혔다는 뜻이므로, 날짜를 증가시키지 않는다.
  • 안익은 토마토가 없다면 걸린 날짜를, 남아있다면 -1을 리턴한다.

결과

메모리	실행 시간
166124KB	792ms

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

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

        String[] information = br.readLine().split(" ");
        int col = Integer.parseInt(information[0]);
        int row = Integer.parseInt(information[1]);

        TomatoBox tomatoes = new TomatoBox(row, col);

        for (int i = 0; i < row; i++) {
            tomatoes.putTomatoes(i, br.readLine().split(" "));
        }

        int days = tomatoes.getAllTomatoRipenDay();
        bw.write(Integer.toString(days));

        bw.flush();
        bw.close();
    }
}

class TomatoBox {
    private int[][] tomatoBox;
    private int boxWidth;
    private int boxHeight;
    Queue<Location> ripenTomatoes;
    private int unripeTomatoes = 0;

    public TomatoBox(int row, int col) {
        this.boxHeight = row;
        this.boxWidth = col;
        this.tomatoBox = new int[boxHeight][boxWidth];
        this.ripenTomatoes = new LinkedList<>();
    }

    public void putTomatoes(int row, String[] tomatoRow) {
        for (int i = 0; i < boxWidth; i++) {
            tomatoBox[row][i] = Integer.parseInt(tomatoRow[i]);

            if (tomatoBox[row][i] == 0) {
                unripeTomatoes += 1;
            } else if (tomatoBox[row][i] == 1) {
                ripenTomatoes.offer(new Location(row, i));
            }
        }
    }

    public int getAllTomatoRipenDay() {
        if (unripeTomatoes == 0) {
            return 0;
        }

        int days = 0;
        Location[] direction = { new Location(-1, 0), new Location(1, 0), new Location(0, -1), new Location(0, 1) };
        Queue<Location> newRipenTomatoes = new LinkedList<>();

        while (!ripenTomatoes.isEmpty()) {
            Location ripenTomato = ripenTomatoes.poll();

            for (int i = 0; i < 4; i++) {
                int nextCol = ripenTomato.col + direction[i].col;
                int nextRow = ripenTomato.row + direction[i].row;

                if (nextCol < 0 || nextCol >= boxWidth || nextRow < 0 || nextRow >= boxHeight) {
                    continue;
                }

                if (tomatoBox[nextRow][nextCol] == 0) {
                    tomatoBox[nextRow][nextCol] = 1;
                    unripeTomatoes -= 1;
                    newRipenTomatoes.offer(new Location(nextRow, nextCol));
                }
            }

            if (ripenTomatoes.isEmpty() && !newRipenTomatoes.isEmpty()) {
                days += 1;
                while (!newRipenTomatoes.isEmpty()) {
                    ripenTomatoes.offer(newRipenTomatoes.poll());
                }
            }
        }

        return unripeTomatoes == 0 ? days : -1;
    }
}

class Location {
    int col;
    int row;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
}