7576 토마토 (JAVA)

• Queue에 정수 두개(x좌표 y좌표)를 넣기 위해 Point 라는 int형 멤버변수 두개를 갖는 클래스를 사용했다.
• 여러개의 시작점을 가질 수 있는 문제다. 그래서 ArrayList에 시작점이 될 수 있는(1이 존재하는) 모든 점의 좌표를 넣어두고, 시작할때 Queue에 모두 때려넣었다.

import java.util.*;
public class Main {

	/* 좌표를 갖는 클래스 */
    static class Point{
        int hei;
        int wid;
        public Point(int hei, int wid) {
            this.hei = hei;
            this.wid = wid;
        }
    }

    static int w,h;
    static int[][] graph;
    static boolean[][] ch;
    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,1,-1,0};
    static ArrayList<Point> init;	// 초기 행렬에서 1의 위치를 모두 담는 ArrayList
    static int bfs(){
        int L = 0;
        Queue<Point> q = new LinkedList<>();
        for(Point p : init) {	// 초기 1의 위치 모두 Queue에 offer
            ch[p.hei][p.wid] = true;
            q.offer(p);
        }
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; ++i){
                Point v = q.poll();
                for(int j=0; j<dx.length; ++j){
                    int vhei = v.hei + dy[j];
                    int vwid = v.wid + dx[j];
                    if(vhei >= 0 && vwid >= 0
                    && vhei < h && vwid < w
                    && !ch[vhei][vwid] && graph[vhei][vwid]==0){
                        ch[vhei][vwid] = true;	// 들어간 자리를 체크배열에 표시한다.
                        graph[vhei][vwid] = 1;	// graph에 들어간 자리는 1로 만든다.
                        q.offer(new Point(vhei, vwid));
                    }
                }
            }
            L++;
        }
        return L;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        w = sc.nextInt();
        h = sc.nextInt();
        graph = new int[h][w];
        ch = new boolean[h][w];

        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                graph[i][j] = sc.nextInt();

        init = new ArrayList<>();
        
        // 초기 행렬에서 '1'의 위치를 찾아 ArrayList에 넣는다.
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if(graph[i][j] == 1)
                    init.add(new Point(i, j));
            }
        }

        
        int answer = bfs()-1;
        
        /* bfs 진행 후, graph에 0이 하나라도 남아있다면 done -> false */
        boolean done = true;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if(graph[i][j] == 0)
                    done = false;
            }
        }

        if(done)    // done이 true면 BFS로 반환받은 레벨값 출력
            System.out.println(answer);
        else
            System.out.println(-1);
    }
}