[Java] 7576번. 토마토 (#너비우선탐색 BFS)

문제링크 : https://www.acmicpc.net/problem/7576

BFS : 시작점을 기준으로 계속 가장 가까운 노드부터 순차로 탐색하는 탐색방법

import java.io.*;
import java.util.*;

public class Main {	
	
	static int day = 0; // 일자 변수
	static int[] dr = new int[] {1, -1, 0, 0}; //탐색범위 (행)
	static int[] dc = new int[] {0, 0, 1, -1}; //탐색범위 (열)
	static boolean[][] map; //탐색여부 체크배열 (익음,없음 : false, 안익음 : true)
	static Queue<int[]> que; //탐색후보자를 담는 배열
	static int m, n;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		map = new boolean[n+2][m+2]; // 탐색이 경계를 넘어가는 것을 방지하기 위해 +2 크기로 잡음
		que = new LinkedList<>();
		for(int i = 1 ; i <= n ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1 ; j <= m ; j++) {
				switch(Integer.parseInt(st.nextToken())) {
					case 0 :
						map[i][j] = true; // 안익은 토마토면 탐색해야므로 true
						break;
					case 1 :						
						que.add(new int[] {i,j}); //익은 토마토면 탐색의 시작점이므로 que에 담기				
				}
			}
		}
		while(!que.isEmpty()) { //탐색 시작점이 있으면 계속 돌기
			Queue<int[]> temp = new LinkedList<>(que); //임시 큐에 옮기기
			que.clear(); // 원래 큐 비우기
			dayThrou(temp); // 하루 보내기~
		}
		if(isExistZero()) {System.out.println(-1); return;}
		else System.out.println(day);		
	}	
	
    //하루 보냈을 때 토마토 익는 알고리즘
	public static void dayThrou(Queue<int[]> temp) {
		for(int[] arr : temp) { //하루를 보내고 안익은 토마토를 체크한 후 위치를 큐에 담기
			for (int i = 0 ; i < 4 ; i++) {
				if(map[arr[0]+dr[i]][arr[1]+dc[i]] == true) {
					que.add(new int[] {arr[0]+dr[i], arr[1]+dc[i]});
					map[arr[0]+dr[i]][arr[1]+dc[i]] = false;
				}
			}		
		}
		if(!que.isEmpty()) day++; // 새롭게 익은 토마토가 없으면 day++
	}
	
    //출력 전에 안익은 토마토가 있는지 체크하는 함수
	public static boolean isExistZero() {
		for(int i = 1 ; i <= n ; i++) {
			for (int j = 1 ; j <= m ; j++ ) {
				if(map[i][j] == true) return true;
			}
		}
		return false;
	}		
}