[백준] CLASS3 7576 토마토 - JAVA [자바]

안녕하세요. 이번에는 백준 7576 토마토 문제를 풀어보려고 합니다.

 

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

7576번: 토마토

---

Problem

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

사진 1. 문제

---

Solution

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

public class Main {
    
    static int N, M;
    static int[][] box;
    static int[] dx = {-1, 0 , 1 , 0};
    static int[] dy = {0, -1 , 0, 1};
    static Queue<Tomato> q = new LinkedList<>();
    
    public static class Tomato {
        int x, y;
        
        Tomato(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        box = new int[N][M];
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            for(int j = 0; j < M; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());        
                
                if(box[i][j] == 1) {
                    q.offer(new Tomato(i, j));        
                }
            }
        }
        
        System.out.println(bfs());
    }
    
    static int bfs() {        
        while(!q.isEmpty()) {
            Tomato t = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = dx[i] + t.x;
                int ny = dy[i] + t.y;
                
                if(nx < N && nx >= 0 && ny < M && ny >= 0) {
                    if(box[nx][ny] == 0) {
                        q.offer(new Tomato(nx, ny));
                        
                        box[nx][ny] = box[t.x][t.y] + 1;
                    }            
                }
            }
        }
        
        int result = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(box[i][j] == 0 ) {
                    return -1;
                }
                    
                result = Math.max(result, box[i][j]);
            }
        }
        
        // 처음 box에 익지 않은 토마토가 없는 경우
        if(result == 1) {
            return 0;    
        }
            
        // 토마토의 첫 시작을 1로 했으니 -1 해야 날짜가 계산된다.
        return result - 1;
    }
}

 이번 문제는 토마토가 익는데 필요한 최소 일수를 구하는 문제이다. 그러면 처음에는 BFS를 활용해서 토마토를 익히는 코드를 구현하고, 토마토가 잘 익었는지 확인하는 코드를 구현하면 된다.

 

구현 요소

1. 토마토가 익는 코드

2. 토마토가 잘 익었는지 확인하는 코드

 

1. 토마토가 익는 코드

	while(!q.isEmpty()) {
            Tomato t = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = dx[i] + t.x;
                int ny = dy[i] + t.y;
                
                if(nx < N && nx >= 0 && ny < M && ny >= 0) {
                    if(box[nx][ny] == 0) {
                        q.offer(new Tomato(nx, ny));
                        
                        box[nx][ny] = box[t.x][t.y] + 1;
                    }            
                }
            }
        }

 

2. 토마토가 잘 익었는지 확인 하는 코드

        int result = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(box[i][j] == 0 ) {
                    return -1;
                }
                    
                result = Math.max(result, box[i][j]);
            }
        }
        
        // 처음 box에 익지 않은 토마토가 없는 경우
        if(result == 1) {
            return 0;    
        }
            
        // 토마토의 첫 시작을 1로 했으니 -1 해야 날짜가 계산된다.
        return result - 1;

---

Performance

사진 2. 실행 결과