백준 7576 - 토마토

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

7576번: 토마토

문제 설명

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

문제 풀이

BFS를 진행하면서, 토마토를 익힌다. 단 , depth를 고려하면서 몇번 진행되었는지 cnt를 세주면서 진행했다. 토마토가 다 익었는지 확인하는 check_zero 메서드를 활용하고 다 익었다면 더이상 BFS를 진행하지 않고 return 하도록 BFS 탐색 시작 전에 항상 체크한다.

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayDeque;
	import java.util.Queue;
	import java.util.StringTokenizer;
	
	public class Main {
		static class Point {
			public Point(int x, int y) {
				this.x = x;
				this.y = y;
			}
	
			@Override
			public String toString() {
				return "Point [x=" + x + ", y=" + y + "]";
			}
	
			int x,y;
			
		}
		static int N, M, cnt;
		static int[][] map;
		static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
		static Queue<Point> queue = new ArrayDeque<>();
		public static void main(String[] args) throws IOException {
			// TODO Auto-generated method stub
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer 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());
					if(map[i][j] == 1) queue.add(new Point(i,j));
				}
			}
			BFS();
			System.out.println(cnt);
		}
		public static void BFS() {
			boolean[][] visited = new boolean[N][M];
			while(!queue.isEmpty()) {
				int size = queue.size();
				if(check_zero()) return;
				for(int depth=0; depth<size; depth++) {
					Point temp = queue.poll();
					for(int dir=0; dir<4; dir++) {
						int nx = temp.x+deltas[dir][0];
						int ny = temp.y+deltas[dir][1];
						if(nx<0 || N<=nx || ny<0 || M<=ny || visited[nx][ny] || map[nx][ny]==-1 || map[nx][ny]==1) continue;
						map[nx][ny] = 1;
						visited[nx][ny] = true;
						queue.add(new Point(nx,ny));
					}
				}
				cnt++;
			}
	//		System.out.println(cnt-1);
			if(!check_zero()) {
				cnt = -1;
				return;
			}
		}
		
		public static boolean check_zero() {
			for(int i=0; i<N; i++) {
				for (int j = 0; j < M; j++) {
					if(map[i][j]==0) return false;
				}
			}
			return true;
		}
	}