G7576. 토마토

문제

제출 코드

• 사용 알고리즘 : bfs

전형적인 bfs 구현 문제. dfs로도 풀이 가능해 보인다.

package gold;

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 G7576_tomato {
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};

	static class Tomato{
		int i, j;
		Tomato(int i, int j){
			this.i = i;
			this.j = j;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		int[][] box = new int[N][M];
		Queue<Tomato> queue = new LinkedList<Tomato>();
		int remains = 0;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if(box[i][j]==0) remains++;
				else if(box[i][j]==1) queue.add(new Tomato(i, j));
			}
		}

		int time = 0;
		loop : while(!queue.isEmpty()) {
			if(remains==0) break;
			time++;
			int size = queue.size();
			for(int i=0; i<size; i++) {
				Tomato now = queue.poll();
				for(int d=0; d<4; d++) {
					int ni = di[d] + now.i;
					int nj = dj[d] + now.j;
					if(ni<0 || ni>=N || nj<0 || nj>=M || box[ni][nj]!=0) continue;
					box[ni][nj] = 1;
					queue.add(new Tomato(ni, nj));
					if(--remains==0) break loop;
				}
			}
		}
		if(remains!=0) System.out.println(-1);
		else System.out.println(time);
	}

}