[백준] 7576번 : 토마토

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

7576번: 토마토

 

문제 해석

N * M 크기의 창고에 토마토가 존재합니다.

창고는 익은 토마토, 익지 않은 토마토 , 빈 공간으로 이루어집니다.

익은 토마토는 4방향(상, 하, 좌, 우)으로 익지 않은 토마토에게 영향을 주며 하루가 지나면 토마토를 익게 만듭니다.

며칠이 지나면 토마토가 다 익는지 최소 일수를 알고 싶어 합니다.

처음부터 토마토가 모두 익어있다면 0을 출력하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력합니다.

 

문제 풀이 전 설계

BFS 탐색 문제라고 생각이 들었습니다.

큐에 현재 창고에 존재하는 익은 토마토의 좌표를 넣어준 뒤 큐가 빌 때까지 반복합니다.

그리고 시간이 얼마나 지났는지 필요하기 때문에 Pos 클래스에 x, y좌표와 depth를 도입하여 시간을 확인합니다.

 

코드

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_7576_토마토 {

	static class Pos {
		int y;
		int x;
		int depth;

		public Pos(int y, int x) {
			super();
			this.y = y;
			this.x = x;
			this.depth = 0;
		}

		public Pos(int y, int x, int depth) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + ", depth=" + depth + "]";
		}

	}

	static final int RIPE_TOMATO = 1;
	static final int UNRIPE_TOMATO = 0;
	static final int EMPTY = -1;
	static final int DIRECTION = 4;
	static int[][] warehouse;
	static boolean[][] visited;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };	
	static int width, height;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		width = Integer.parseInt(st.nextToken());
		height = Integer.parseInt(st.nextToken());

		warehouse = new int[height][width];
		visited = new boolean[height][width];

		for (int y = 0; y < height; y++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int x = 0; x < width; x++) {
				warehouse[y][x] = Integer.parseInt(st.nextToken());
			}
		}
		
		// BFS 탐색
		// 보관후 하루가 지나면 익은 토마토들의 인접한 곳에 있지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
		// 이때 인접은 상,하,좌,우
		// BFS Queue에 익은 토마토를 넣을것인가 익지 않은 토마토를 넣을것인가
		// 토마토가 모두 익을 때까지의 최소 날짜를 출력
		int time = BFS();

		if(!isAllRiped()) {
			System.out.println(-1);
			return;
		}
		
		System.out.println(time);
	}

	private static int BFS() {
		Queue<Pos> bfsQ = new LinkedList<Pos>();
		// 큐에 초기값 넣어주기 (현재 창고에 존재하는 익은 토마토의 좌표)
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				if (warehouse[y][x] != RIPE_TOMATO) {
					continue;
				}
				bfsQ.add(new Pos(y, x));
				visited[y][x] = true;
			}
		}
		
		int currentDepth = -1;		
		
		while (!bfsQ.isEmpty()) {	
			
			Pos temp = bfsQ.poll();
			int tempDepth = temp.depth;

			for (int k = 0; k < DIRECTION; k++) {
				
				int tempY = temp.y + dy[k];
				int tempX = temp.x + dx[k];
				
				if (!isValid(tempY, tempX)) {
					continue;
				}
				
				visited[tempY][tempX] = true;
				warehouse[tempY][tempX] = RIPE_TOMATO;
				bfsQ.add(new Pos(tempY, tempX, tempDepth + 1));
				
			}
			currentDepth = tempDepth;
		}
		return currentDepth;

	}
	
	// 좌표가 유효 + 방문되지 않았어야 함 + 주변에 안익은 토마토가 존재해야함.
	private static boolean isValid(int tempY, int tempX) {		
		return (tempY >= 0 && tempX >= 0 && tempY < height && tempX < width && !visited[tempY][tempX]
				&& (warehouse[tempY][tempX] == UNRIPE_TOMATO));
	}
	
	//토마토가 모두 익었는지 확인
	private static boolean isAllRiped() {
		for(int y=0; y<height; y++) {
			for(int x=0; x<width; x++) {			
				if(warehouse[y][x] == UNRIPE_TOMATO) {
					return false;
				}
			}			
		}
		return true;
	}

}