[백준] 7576번 토마토 (JAVA)

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

7576번: 토마토

 

• 문제 이해
• 해결 방법
• 구현 코드

---

문제 이해

 

기본적으로 BFS를 이용한 위, 아래, 좌, 우를 0이면 1로 바꾸는 Flood fill 문제인 것은 알 수 있었다.

이 문제는 BFS의 기본 문제들과는 다르게 Flood fill의 시작 위치가 여러 개인 점이 기본 문제와는 달랐다.

Queue의 특성상 시작 토마토의 위치들인 1인 지점들을 bfs 함수를 실행 하기 이전에 전부 미리 넣어준 후

bfs를 하면 될 것 같다는 점은 쉽게 파악할 수 있었다.

 

그 이후 bfs를 이용해 기존하던 방식으로 각 상자에서 토마토가 1이므로 1의 주변을 익어가게끔 하면 되는 문제였다.

-1인 벽을 처리해주어야 하는 요구사항이 있지만 어차피 bfs를 할 때 0인 조건만 1로 만들어주면 되므로 0일 때만

새로운 토마토 객체를 생성해주면 되었다.

 

 

---

해결 방법

 

bfs를 실행하기 이전에 시작 토마토들인 1의 위치를 전부 Queue에 넣어 주어주어야 했다.

넣어주는 과정은 입력을 받는 과정에서 1이라면 Queue에 행, 열 위치를 알 수 있는 토마토 객체를 생성하여 넣어주었다.

 

추가로 토마토 객체를 생성할 때 인스턴스 변수로 며칠이 지났는지 확인할 수 있는 day를 만들어 주었다.

새로운 객체를 생성할 때 현재 Queue에서 꺼낸 반복문을 돌아가는 객체의 day 인스턴스 변수에 +1 만 해서 새로 객체를 생성할 때 지정해준다면

새로운 토마토가 생성될 때마다 이전 토마토의 day에 +1을 하므로 최소일 수를 알 수 있다.

 

최소일수를 알고자 할 때 모든 객체의 day의 max를 계산하면 시간이 추가로 걸리므로 이 방법보다는 전역 변수에 day를 선언해두고

가장 마지막에 생성되는 객체의 day를 전역변수 day에 저장한다면 그것이 마지막 익는 토마토의 날짜가 될 것이다. 

 

bfs는 2차원 배열을 탐색할 때 자주 처리해주는 2차원 배열의 범위를 벋어 나지 않게 설정해주고, 0이면 토마토 객체를 생성하고

그 부분을 1로 바꿔주어 다시 Queue에 생성되지 않도록 하였다. 0 일 때만 처리하므로 -1 인 벽을 신경 써주지 않아도 된다.

 

 

---

구현 코드

 

import java.io.*;
import java.util.*;
 
public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[][] box ;
    static Queue<toma> q = new LinkedList<>();
    static int day = 0;
 
    public static void main(String[] args) throws IOException {
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
 
        M = Integer.parseInt(st.nextToken()); 
        N = Integer.parseInt(st.nextToken()); 
        box = new int[N][M];
        for(int i = 0 ; i<N; i++){
            String low = br.readLine();
            st = new StringTokenizer(low);
            for( int j = 0; j<M; j++){
                String bbb = st.nextToken();
                box[i][j] = Integer.parseInt(bbb);
                if(bbb.equals("1"))
                    q.offer(new toma(i, j, 0));
            }
        }
        
        bfs();
 
        for(int i =0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(box[i][j] == 0)
                    day = -1;
            }
        }
        if( day != -1 ){
            System.out.println(day - 1);
        }else
            System.out.println(day);
    }// end main
 
    public static void bfs(){
        int[] xrange = {1, -1, 0, 0};
        int[] yrange = {0, 0, 1, -1};
 
        while(!q.isEmpty()) {
            toma tomas = q.poll();
            int nx = tomas.x;
            int ny = tomas.y;
            int days = tomas.day + 1;
            for (int i = 0; i < 4; i++) {
                int nnx = nx + xrange[i];
                int nny = ny + yrange[i];
                if (nnx >= 0 && nnx < N && nny >= 0 && nny < M){
                    day = days;
                    if (box[nnx][nny] == 0) {
                        q.offer(new toma(nnx, nny, days));
                        box[nnx][nny] = 1;
                    }
                }
            }
        }
    }
} // end class
 
class toma{
    int x;
    int y;
    int day;
 
    toma(int x, int y, int day){
        this.x = x;
        this.y = y;
        this.day = day;
    }
}