[백준] 7576 토마토 [자바]

---

https://jdselectron.tistory.com/55

[백준 7576, c++] 토마토(bfs)

---

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

public class Main {
	static int[][] xy;
	static int[] x_move = {-1,0,1,0};
	static int[] y_move = {0,-1,0,1};
	static int tomato_cnt = 0;
	static int entire = 0;
	static boolean[][] visit;
	static int [][] cnt;
	static Queue<Integer> q = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken()); //y
		int M = Integer.parseInt(st.nextToken()); //x
		xy = new int[M][N];
		visit = new boolean[M][N];
		cnt = new int[M][N];
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				int a = Integer.parseInt(st.nextToken());
				xy[i][j] = a;
				if(a != -1)
					entire++; //마지막에 개수 비교를 위한
				if(a == 1) {
					q.add(i);
					q.add(j);
					tomato_cnt++;
					visit[i][j] = true;
				}
			}
		}
		bfs(M,N);
	}
	static void bfs(int n, int m) {
		int dis = 3;
		boolean swi = true;
		while(!q.isEmpty()) {
			int x = q.poll();
			int y = q.poll();
			for(int i = 0; i < 4; i++) {
				int tx = x+x_move[dis];
				int ty = y+y_move[dis];
				if(tx >= 0 && tx < n && ty >= 0 && ty < m) {
					if(xy[tx][ty] == 0 && visit[tx][ty] == false) {
						q.add(tx);
						q.add(ty);
						tomato_cnt++;
						xy[tx][ty] = 1;
						visit[tx][ty] = true;
						cnt[tx][ty] = cnt[x][y] + 1;
					}
				}
				dis = change(dis);
			}
		}
		if(entire == 0)
			System.out.println(-1);
		else if(entire != tomato_cnt)
			System.out.println(-1);
		else {
			int result = 0;
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(result < cnt[i][j])
						result = cnt[i][j];
				}
			}
			System.out.println(result);
		}
	}
	static int change(int n) {
		if(n == 0)
			return 3;
		else
			return n-1;
	}
}