[BJ] 7576 토마토 Java

백준 7576 토마토

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

7576번: 토마토

아이디어

• BFS로 탐색을 하는데, 익은 토마토와 인접한 곳부터 익어야하기 때문에 큐에 익은 토마토를 미리 다 넣어준다.
• 2차원 배열로 만들어서 탐색하는데, 1인 곳은 새로 정의한 Tomato 클래스로 미리 큐에 넣는다
• 그렇게 되면 1과 인접한 곳부터 모두 탐색하는데 0이 아닌곳은 탐색하지 않음
• 마지막에 배열을 확인해서 익지 않은 토마토가 있는지, 아니면 모두 익었는지 확인
• 토마토가 익는 일수에서 -1은 첫날에 있는 토마토는 일수에 카운팅 하지 않기 때문이다

코드

package baekjoon;
import java.util.*;

class Tomato {
    private int x, y;
    public Tomato(int x, int y) {
        this.x=x;
        this.y=y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}



class BJ7576 {
    static boolean visited[][];
    static int[][] map;
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,-1,1};
    static int n,m,answer;
    static Queue<Tomato> q = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[m][n];

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (map[i][j] == 1) q.offer(new Tomato(i,j));
            }
        }
        int max = Integer.MIN_VALUE;
        BFS();

//        for (int i=0; i<m; i++) {
//            System.out.println(Arrays.toString(map[i]));
//        }

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
                else max = Math.max(map[i][j], max);
            }
        }
        System.out.println(max-1);
    }

    public static void BFS() {
        while (!q.isEmpty()) {
            Tomato tmp = q.poll();
            int tx = tmp.getX();
            int ty = tmp.getY();

            for (int i=0; i<4; i++) {
                int nx = tx + dx[i];
                int ny = ty + dy[i];

                if (nx>=0 && nx<m && ny>=0 && ny<n) {
                    if (map[nx][ny] == 0) {
                        answer++;
                        map[nx][ny] = map[tx][ty] + 1;
                        q.offer(new Tomato(nx, ny));
                    }
                }
            }
        }
    }

}