[백준] 7576 토마토

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

7576번: 토마토

Pair 클래스는 좌표를 저장하기 위한 클래스.  check 함수는 2차원 배열 map 을 돌면서 0이 있으면(익지 않은 토마토가 있으면) -1 출력하기 위한 함수  Queue 자료구조의 제네릭을 Pair 클래스로 지정    제네릭: 클래스 내부에서 사용할 데이터 타입을 외부에서 지정하는 기법  BFS : 너비우선 탐색, 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법으로 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 너비 우선 탐색을 적용(완전 탐색)  1. 큐가 비어있지 않을 때 동안 반복 , 큐가 비면 그만  큐의 사이즈 지정, 큐한번 돌아가는 동안 DAY 변수가 1씩 증가  열이 큐의 사이즈까지 반복하면서   2. poll() 메소드를 이용한 요소의 반환 및 제거 -> 큐에있는 객체 하나 뽑아서 p에 저장  3. 방문 표시  사방 탐색 - 행 기준  nx,ny 는 다음 좌표  다음 좌표가 배열의 범위를 넘지 않으면서 방문하지 않았으면서 0이면 1을 대입하고  4. 다음 좌표를 큐에 추가

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
	static int M, N, DAY = 0;
	static int[][] map, dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
	static boolean[][] visited;
	static Queue<Pair> queue = new LinkedList();

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();

		map = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				if (map[i][j] == 1) {
					queue.add(new Pair(i, j));
				}
			}
		}

		BFS();

		if (!check()) {
			System.out.println("-1");
			return;
		} else
			System.out.println(DAY - 1);

	}// end of main

	public static void BFS() {
		while (!queue.isEmpty()) {
			int len = queue.size();
			DAY++;

			for (int j = 0; j < len; j++) {
				Pair p = queue.poll();
				visited[p.x][p.y] = true;
				for (int i = 0; i < 4; i++) {

					int nx = p.x + dir[i][0];
					int ny = p.y + dir[i][1];
					
					if (isInside(nx, ny) && !visited[nx][ny] == true && map[nx][ny] == 0) {
						map[nx][ny] = 1;
						queue.offer(new Pair(nx,ny));
					}
				}
			}
		}

	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}

	public static boolean check() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)
					return false;
			}
		}
		return true;
	}
}// end of class

class Pair {
	int x;
	int y;

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

}
//2차원 배열 - isInside
//4방
//최소 일수- BFS ,Queue