[백준 7576] 토마토 (JAVA)

백준 7576번 문제 - 토마토

7576번: 토마토

---

문제 분석

 

 

• 창고에 토마토가 격자모양의 상자들에 보관되어있다.
• 익은 토마토는 하루가 지나면 인접한 곳에 있는 토마토도 익게 한다.
  • 인접한 곳은 위, 아래, 왼쪽, 오른쪽 네 방향에 있는 토마토를 의미
• 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 
  • 익은 토마토 : 1
  • 익지 않은 토마도 : 0
  • 토마토 없음 : -1 (일부 칸에는 토마토가 들어있지 않을 수도 있다.)

---

해결 포인트

 

• BFS 문제
• 익은 토마토들을 리스트로 제작한다.
  • ArrayList<Point> ripeTomato = new ArrayList<>();
• ripeTomato에 담겨져있는 위치 정보(Point)를 Queue에 넣는다.
• 근처 토마토 확인 후 안익었으면 Queue에 삽입
• 큐에 담겨져 있는 모든 Location을 확인했을 경우 count 증가
• BFS 이후 토마토 배열에 0이 없는지 체크 (익지 않은 토마토가 없는지)

---

코드

 

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

public class Main {
    public static int N,M;
    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int [][] tomatos = new int[M][N];

        ArrayList<Point> ripe = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                tomatos[i][j] = Integer.parseInt(st.nextToken());
                if(tomatos[i][j] == 1) {
                    ripe.add(new Point(i, j));
                }
            }
        }

        int count = BFS(ripe, tomatos);

        boolean isAllRipe = true;
        for (int i = 0; i < M; i++) {
            if(!isAllRipe)
                break;
            for (int j = 0; j < N; j++) {
                if(tomatos[i][j] == 0) {
                    isAllRipe = false;
                    break;
                }
            }
        }

        if(isAllRipe)
            bw.write(count +"\n");
        else
            bw.write("-1\n");

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

    public static int BFS(ArrayList<Point> ripe, int [][] tomatos) {
        int [] dx = {0,0,1,-1};
        int [] dy = {1,-1,0,0};

        int count = 0;
        Queue<Point> queue = new LinkedList<>();

        for (int i = 0; i < ripe.size(); i++) {
            queue.add(ripe.get(i));
        }

        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                Point value = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = value.x + dx[j];
                    int ny = value.y + dy[j];

                    if(checkRound(nx, ny) && tomatos[nx][ny] == 0) {
                        tomatos[nx][ny] = 1;
                        queue.add(new Point(nx, ny));
                    }
                }
            }
            count++;
        }

        return count-1;
    }

    public static boolean checkRound(int x, int y) {
        return x >= 0 && y >= 0 && x < M && y < N;
    }
}