[Java] 백준 7576 : 토마토

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

7576번: 토마토

---

 

-1은 토마토가 없는 칸

1은 익은 토마토

0은 안 익은 토마토 일 때, 

며칠이면 상자 안에 있는 토마토가 모두 익는지에 대한 문제이다. 

 

bfs를 사용해 문제를 풀면 된다. 

그러기 위해서는 우선 토마토의 상태를 입력받는 코드를 작성해야 하는데, 익어있는 토마토의 xy좌표를 큐에 저장해야 한다. 

	for (int i = 0; i < N; i++) {
			String[] nums = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				box[i][j] = Integer.parseInt(nums[j]);
				if (box[i][j] == 1) {
					qu.add(new Point(i, j));
				}
			}
		}

그리고 입력받은 토마토좌표를 가지고 bfs를 진행하면 된다. 

큐에 들어있는 이미 익어 있는 토마토 좌표와 인접한 토마토들에 접근하여 토마토가 안익어 있다면 

큐에 그 토마토의 좌표를 넣어주고, 배열에 며칠째에 익었는지 넣어준다. (이동해온 좌표에 들어있던 값에+1 한 값을 저장해 준다.)

이 방법으로 큐가 모두 비어있게 될 때까지 진행을 해준다. 

예제 입력을 사용하여 진행하면 아래와 같이 배열에 값이 저장되어 있게 된다. 

 

그리고 변한 값을 가지고 있는 배열을 가지고 출력을 하면 된다. 

배열을 0,0부터 검사했을 때,

최댓값이 1인 경우 이미 모튼 토마토가 익어 있었다는 의미이므로 0을 출력하고,

0이 존재하는 경우 절대 익지 못하는 토마토가 존재한다는 의미이므로 -1을 출력,

이외의 값이 존재한다면 토마토가 모두 익었다는 의미이므로 그 값을 출력하면 된다. 

단, 며칠이 걸렸는지 출력할 때 -1을 해주고 출력해줘야 한다. (시작이 1 이였으므로)

---

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

public class Main {

	static int N, M, days;
	static int[][] box;
	static boolean[][] visit;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };
	static Queue<Point> qu = new LinkedList<>();

	static class Point {
		int x, y;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		M = Integer.parseInt(str[0]); // M 상자의 가로
		N = Integer.parseInt(str[1]); // N 상자의 세로
		box = new int[N][M];
		visit = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String[] nums = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				box[i][j] = Integer.parseInt(nums[j]);
				if (box[i][j] == 1) {
					qu.add(new Point(i, j));
				}
			}
		}

		bfs();
		checkTomato();
	}// main()

	static void bfs() {
		while (!qu.isEmpty()) {
			Point tmp = qu.poll();
			int x = tmp.x;
			int y = tmp.y;

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

				if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
					if(box[nx][ny]==0) {
						qu.add(new Point(nx,ny));
						box[nx][ny]=box[x][y]+1;
					}
				}
			}
		}	
		
	}//bfs()
	
	static void checkTomato() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(box[i][j]==0) {
					System.out.println(-1);
					return;
				}
				days=Math.max(days,box[i][j]);
			}
		}
		
		if(days==1)
			System.out.println(0);
		else {
			System.out.println(days-1);
		}
		
	}//checkTomato()

}// class Main