백준 - 7576번 - 토마토

7576번

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

public class Main{

	static class Tomato {
		int x;
		int y;
		int day;

		public Tomato(int x, int y, int day) {
			this.x = x;
			this.y = y;
			this.day = day;
		}
	}
	static int[][] box;
	static int n, m;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		box = new int[m+1][n+1];

		for (int i = 1; i<=m; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 1; j<=n; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		bfs();
	}

	static void bfs() {

		Queue<Tomato> queue = new LinkedList<>();
		int day = 0;

		for (int i = 1; i<m+1; i++) {
			for (int j = 1; j<n+1; j++) {
				if (box[i][j] == 1) {
					queue.add(new Tomato(i, j, 0));
				}
			}
		}

		while (!queue.isEmpty()) {
			Tomato tomato = queue.poll();
			day = tomato.day;

			for (int i = 0; i<4; i++) {
				int nx = tomato.x + dx[i];
				int ny = tomato.y + dy[i];

				if (nx > 0 && ny > 0 && nx <= m && ny <=n) {
					if (box[nx][ny] == 0) {
						box[nx][ny] = 1;
						queue.add(new Tomato(nx, ny, day+1));
					}
				}
			}
		}

		if (checkTomato()) {
			System.out.println(day);
		} else {
			System.out.println(-1);
		}
	}

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

풀이

---

2차원 배열로 0 과 1이 입력된다. 1의 가로 세로 위 아래에 있는것들은 하루지나면 0인것들이 1로 바뀐다. 2차원 배열이 모두 1이되기까지는 몇일이 걸리는지 구하는 문제다.

Tomato 클래스를 만들어 가로열, 세로열, 날짜를 변수로 받는다.

Tomato 형태의 큐를 선언하고 2차원 배열에 1인경우를 찾아 큐에 tomato 형식으로 집어넣는다.

queue.add(new Tomato(nx, ny, day+1));

이 표현이 참 생소했다.

아무튼 이제 bfs 탐색을 시작한다 큐에 저장된 정보의 가로 세로 위 아래가 0이라면 1로 바꾸고 큐에 day만 +1 해서 담는다.

마지막으로 2차원배열을 확인해서 0이 있는 경우가 있다면 -1을 아니라면 tomato.day를 출력해준다.

생각지도 못한 아주 기발한 방법이다...