[BOJ 7576] 토마토 (Java)

문제

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

7576번: 토마토

BOJ7576 토마토

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

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

 

입력: 1 익은 토마토, -1 비어있는 칸, 0 안익은 토마토

 

풀이

BFS로 풀었다. 중요한 점은 처음에 익은 토마토들을 모두 Queue에 넣어서 탐색해야 한다는 점이다.

그래야 동시에 넓이 탐색을 시작할 수 있다.

        box = new int[n+1][m+1];
        done = new boolean[n+1][m+1];
        que = new LinkedList<Integer>();
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; j++){
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j] == 1){
                    que.offer(i);
                    que.offer(j);
                    que.offer(0);
                }
            }
        }

 

 

소스코드

package bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ7576 {

    public static int[][] box;
    public static boolean[][] done;
    public static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static int m;
    public static int n;
    public static Queue<Integer> que;

    public static void main(String[] args) throws Exception {
        input();
    }

    public static void input() throws Exception {
        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+1][m+1];
        done = new boolean[n+1][m+1];
        que = new LinkedList<Integer>();
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; j++){
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j] == 1){
                    que.offer(i);
                    que.offer(j);
                    que.offer(0);
                }
            }
        }

        int minDays = bfs();
        boolean allDone = true;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(box[i][j] == 0){
                    allDone = false;
                    break;
                }
            }
        }
        System.out.println(allDone? minDays : -1);
    }

    public static int bfs(){
        int minDays = 0;
        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();
            int depth = que.poll();
            minDays = Math.max(depth, minDays);

            for(int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                if(isValid(nx, ny)){
                    box[nx][ny] = 1;
                    que.offer(nx);
                    que.offer(ny);
                    que.offer(depth+1);
                }
            }
        }
        return minDays;
    }

    public static boolean isValid(int x, int y){
        if(x < 1 || y < 1 || x > n || y > m ) return false;
        if(box[x][y] == 1) return false;
        if(box[x][y] == -1) return false;
        return true;
    }
}