백준 7576번 : 토마토(Java)

 

7576번: 토마토

---

[풀이]

- BFS를 이용하여 풀었습니다.
- 익은 토마토가 가지고 있는 토마토에 전부 영향을 줘야 하기 때문에 queue에 담긴 위치를 기반으로 모든 토마토를 익게 할 때까지 횟수를 기록해야합니다.
  - 이때, 횟수는 이전에 arr 2차원 배열에 기록된 것에 +1 함으로써 기록할 수 있습니다.
- 주어진 값에서 1(익은 토마토)인 경우 모두 큐에 담아 이 큐에 담긴 Point 값이 시작 지점이 됩니다.
- 이후, queue에서 하나씩 값을 꺼내 익지 않은 토마토(0)일 경우, 새로 queue에 담으며 queue가 빌 때까지 이 과정을 반복합니다.
- 만약, 처음부터 이미 모두 익은 토마토일 경우 while 반복문을 실행하지 않아도 되기때문에 저는 check()메소드로 먼저 확인을 했습니다.
- 마지막으로, 값을 전체 확인하며 아직 익지 않은 토마토가 있을 경우 -1을 반환하고 이외에 정상적으로 while문이 실행되었을 경우에는 최종 count를 반환합니다.

---

[코드]

 

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 m, n;
	static int[][] arr;
	static Queue<Point> queue = new LinkedList<>();
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};

	static class Point {

		int x, y;

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

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

		arr = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 1) {
					queue.offer(new Point(i, j));
				}
			}
		}
		System.out.println(solve());
	}

	public static int solve() {
		int result = Integer.MIN_VALUE;
		if (check()) {
			return 0;
		}
		while (!queue.isEmpty()) {
			Point poll = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nextX = poll.x + dx[i];
				int nextY = poll.y + dy[i];

				if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < m) {
					if (arr[nextX][nextY] == 0) {
						queue.offer(new Point(nextX, nextY));
						arr[nextX][nextY] = arr[poll.x][poll.y] + 1;
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 0) {
					return -1;
				}
				result = Math.max(result, arr[i][j]);
			}
		}
		return result - 1;
	}

	public static boolean check() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] != 1) {
					return false;
				}
			}
		}
		return true;
	}
}