토마토

📍 문제 설명

 

💡 접근

예전 강의에서 배웠던 문제

BFS의 시작지점이 여러개다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, v, e, k, answer, cnt;
    static int[][] board;
    static int[] arr;
    static long[] dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Integer> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    static Queue<Point> q = new LinkedList<>();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        m = kb.nextInt();
        n = kb.nextInt();
        kb.nextLine();
        board = new int[n][m];
        visited = new boolean[n][m];
        boolean flag = false;
        for(int i = 0; i < n; i++) {
            String[] s = kb.nextLine().split(" ");
            for(int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(s[j]);
                if(board[i][j] == 1) {
                    q.offer(new Point(i, j));
                    visited[i][j] = true;
                }
                if(board[i][j] == 0) flag = true;
            }
        }
        if(!flag) {
            System.out.println(0);
            System.exit(0);
        }
        T.solution();
        //board에 0이 있으면 -1
        //board에 0이 없으면 최댓값
        //flag가 false면 이미 다 익어있는 상태
        int max = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] > max) max = board[i][j];
                if(board[i][j] == 0) {
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }
        System.out.println(max);
    }


    private void solution() {
        int cnt = 1;
        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                Point cp = q.poll();
                for(int j = 0; j < 4; j++) {
                    int nx = cp.x + dx[j];
                    int ny = cp.y + dy[j];
                    if(nx<0 || ny<0 || nx>=n || ny>=m || board[nx][ny] == -1) continue;
                    if(!visited[nx][ny]) {
                        visited[nx][ny] = true;
                        board[nx][ny] = cnt;
                        q.offer(new Point(nx, ny));
                    }
                }
            }
            cnt++;
        }
    }

    private static class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}