백준 7576번 토마토 [JAVA]

BFS(너비우선탐색) 문제로 Java 유틸 중 queue를 써서 풀었다.

1이 입력된 x와 y좌표를 먼저 큐에 담고 그 좌표를 poll한 후 상하좌우 중 값이 0인 부분의 x, y좌표를 다시 큐에 넣는다.

이를 반복하고 큐가 비었을 때까지 다음과 같은 과정을 반복한다.

 

해당 과정을 마쳤을 때, 배열에 0이 있으면 -1을 리턴하고

아니면 max에서 -1한 값을 리턴하면 된다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//토마토
public class Main_7576 {
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int M = scan.nextInt();
		int N = scan.nextInt();
		
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, 1, -1};
		int[][] arr = new int[N][M];
		
		Queue<Dot> q = new LinkedList<Dot>();
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				arr[i][j] = scan.nextInt();
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(arr[i][j] == 1) {
					q.add(new Dot(i,j));
				}
			}
		}
		
		while(!q.isEmpty()) {
			Dot dot = q.poll();
			
			for(int i=0; i<4; i++) {
				int nextX = dot.x + dx[i];
				int nextY = dot.y + dy[i];

				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
					continue;
				}
				
				if(arr[nextX][nextY] != 0) {
					continue;
				}

				arr[nextX][nextY] = arr[dot.x][dot.y] + 1;
				q.add(new Dot(nextX, nextY));
			}
		}
		
		  int max = arr[0][0];
		  for(int i=0; i<N; i++) { 
			  for(int j=0; j<M; j++) { 
				  if(arr[i][j] == 0) {
					  System.out.println("-1");
					  return;
				  }else if(max < arr[i][j]) {
					  max = arr[i][j];
				  }
			  } 
		  }
		  
		  System.out.println(max-1);
	}
}

class Dot {
	int x;
	int y;

	Dot(int x, int y) {
		this.x = x;
		this.y = y;
	}
}