[7576] 토마토

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

7576번: 토마토

---

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

class Main {

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

	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));
			}
		}

		if (!check()) {
			System.out.println(DAY);
			return;
		}

		BFS();

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

	public static void BFS() {

		while (!queue.isEmpty()) {
			int len = queue.size();
			DAY++;
//			System.out.println("DAY : " + 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] && map[nx][ny] == 0) {
						visited[nx][ny] = true;
						map[nx][ny] = 1;
						queue.offer(new Pair(nx, ny));
					}
				}
			}
			if(!check()) return;
//			print();
		}
	}
	
	public static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}

	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 true;
			}
		}
		return false;
	}
	
	public static boolean check2() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0)	return false;
			}
		}
		return true;
	}
	
}

class Pair {
	int x;
	int y;

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

---

[문제 풀이]

1. check() 함수는 안익은 토마토가 있는지 확인하는 함수 입니다. 안익은 토마토가 없다면 모든 토마토가 익은 상태이므로 0을 출력합니다.

2. 안익은 토마토가 있다면 BFS를 수행합니다. 한번 BFS를 반복할 때 마다 DAY 를 1씩 증가시켜 줍니다.

3. BFS를 한번 수행할 때 마다 check() 함수로 안익은 토마토가 있는지 검사하고, 모든 토마토가 익었다면 더이상 BFS를 수행하지말고 return 하고 DAY를 출력해줍니다.

4. BFS가 끝나고 check2() 함수를 수행하는데 check2() 함수는 check()와는 반대로 안익은 토마토가 없는지 검사하는 함수입니다. BFS를 수행했는데도 안익은 토마토가 있다면 더이상 토마토를 익힐 수 없으므로 불가능을 뜻하는 -1를 출력하면 됩니다.