BOJ 7576 토마토

문제 분석

- 익은 토마토에서 안익은 토마토로 퍼져나가서 bfs로 풀이했다. 

- 며칠 후에 토마토가 모두 익는지 확인해야하기때문에 Point클래스에 day를 추가하여 관리하였다.

 

 

문제 풀이

1) 상자의 상태를 입력받는다.

2) 익은 토마토(1)의 좌표를 구하여 큐에 삽입한다. 

📌 이때 day를 같이 넣어준다. ∵ 해당 좌표의 토마토가 며칠이 걸려서 익는지 계산하기 위해 영향을 주는 토마토의 day+1을 해줘야하기 때문이다.

3) 큐가 비어있는 상태가 될 때까지 상하좌우를 탐색하여 익힐 수 있는 토마토의 경우 큐에다 넣고 반복한다.

4) 토마토의 상태를 전부 변경 완료하면 출력을 위해 덜 익은 토마토가 있는지 체크한다(chk())

5) 각각 상태에 따라 알맞은 답을 출력한다.

 

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 {
	private static int N, M, ans;
	private static int[][] map;
	private static int[] dr = { -1, 1, 0, 0 }; // 좌우상하
	private static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		input();
	}// main

	static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // for
		if (bfs()) {
			System.out.println(ans);
		} else {
			System.out.println("-1");
		}
	}// input

	static boolean bfs() {

		Queue<Point> q = new LinkedList<>();

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

		while (!q.isEmpty()) {
			Point cur = q.poll();
			int curX = cur.x;
			int curY = cur.y;
			ans = cur.day;

			for (int d = 0; d < 4; d++) { // 상하좌우
				int nx = curX + dr[d];
				int ny = curY + dc[d];
				if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
					if (map[nx][ny] == 0) {
						map[nx][ny] = 1;
						q.add(new Point(nx, ny, ans + 1));
					}

				}
			}
		}

		// 상태 체크
		return chk();
	}// bfs

	private static boolean chk() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}// chk

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

		Point(int x, int y, int day) {
			this.x = x;
			this.y = y;
			this.day = day;
		}
	}// Point-class-end

}// class-end