백준 7576 토마토 (Java)

1. 문제 링크

7576번: 토마토

 

2. 문제 및 입출력예제

 

3. 문제 풀이

큐를 이용해서 풀었다.

익은 토마토를 큐에 넣어두고 하나씩 꺼내면서 사방탐색을 하는 방식이다.

큐가 비어있으면 종료하고 전체 토마토 중 안 익은 토마토가 있으면 -1을 출력한다.

날짜를 저장하기 위해서 day라는 배열을 만들어서 사용했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int N, M;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		M = Integer.parseInt(split[0]);
		N = Integer.parseInt(split[1]);
		int[][] day = new int[N][M];
		map= new int[N][M];
		for(int i=0;i<N;i++) {
			String[] split2 = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(split2[j]);
			}
		}
		
		Queue<int[]> tomato = new ArrayDeque<>();
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] == 1) { 
					day[i][j] = 1; 
					tomato.add(new int[] {i,j});
				}
			}
		}
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		while(!tomato.isEmpty()) {
			int now[] = tomato.poll();
			int x = now[0];
			int y = now[1];
			for(int i=0;i<4;i++) {
				int X = x + dx[i];
				int Y = y + dy[i];
				if(X<0 || Y<0 || X>N-1 || Y>M-1) {
					continue;
				}
				if(map[X][Y]!=0) {
					continue;
				}
				map[X][Y] = map[X][Y] + 1;
				day[X][Y] = day[x][y] + 1;
				tomato.add(new int[] {X, Y});
			}
		}
		boolean flag = true;
		int max = 0;
		out:
		for(int i=0; i<N;i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) {
					flag = false; 
					break out;
				}
				max = Math.max(max, day[i][j]);
			}
		}
		if(flag) {
			System.out.println(max - 1); 
		}
		else {
			System.out.println(-1); 
		}
	}
}