토마토BFS활용

코드

import java.util.*;

class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int n, m;
	static Queue<Point> Q=new LinkedList<>();
	
	static void BFS2(){
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				Point p = Q.poll();
				
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					
					if(nx>=0&&nx<n  && ny>=0&&ny<m && board[nx][ny]==0) {
						board[nx][ny]= 1;
						Q.offer(new Point(nx, ny));
						dis[nx][ny] =dis[p.x][p.y]+1;
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		m=6; //가로 크기
		n=4; //세로 크기
		board=new int[n][m];
		dis=new int[n][m];
		
		int[][] tmp = 
			{{0, 0, -1, 0, 0, 0}
			,{0, 0, 1, 0, -1, 0}
			,{0, 0, -1, 0, 0, 0}
			,{0, 0, 0, 0, -1, 1}};
		
		board = tmp.clone();
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(board[i][j]==1) Q.offer(new Point(i, j));
				//출발점이 여러개라 미리 넣어둠
			}
		}
		
		BFS2();
		
		//0이 하나라도 존재하면 토마토가 모두 익지 못하는 상황
		long count = Arrays.stream(board)
		      .flatMapToInt(Arrays::stream)
		      .filter(value->value==0)
		      .count();
		if(count>0) System.out.println(-1);
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		// 만약 처음부터 모두 익어있다면 자연스럽게 0 출력될 것
		int value = Integer.MIN_VALUE;
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis[i].length; j++) {
				value = Math.max(value, dis[i][j]);
			}
		}
		System.out.println(value);
		for (int[] arr : dis) {
			for (int val : arr) {
				System.out.printf("%2s ",val);
			}
			System.out.println();
		}
		
	}
	static class Point{
		public int x, y;
		Point(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}

---

결과

4
 3  2  0  2  3  3 
 2  1  0  1  0  2 
 3  2  0  2  2  1 
 4  3  4  3  0  0

---

전부 똑같다. 다른 점은 시작점이 여러 개라면 미리 큐에 넣어둔다. 그 차이가 전부다.

문제에서 시작점인 것에 위치값을 준게 아니라 미리 board[x][y] = 1 같이 넣어뒀기에 시작 시 출발 값에 1을 체크할 필요 없다.